露出水面的部分=露出水面的石头个数-自己和前一个都露出水面的个数。

离散，然后把每块石头的高度丢进权值树状数组(+1)；每一个和前一个取min，丢进同一个树状数组(-1)，一次询问，直接看大于当前数的和是多少就好了。

//树状数组 
#include <cstdio>
#include <algorithm>
#define maxn 1000000
#define lowbit(x) (x&-x)
using namespace std;
int ta[maxn], tmp[maxn], q[maxn][3], N, a[maxn], tot, M;
inline int ls(int x){return lower_bound(tmp+1,tmp+tot+1,x)-tmp;}
inline void add(int pos, int v){for(;pos<=tot;pos+=lowbit(pos))ta[pos]+=v;}
inline int sum(int pos)
{
	int ans=0;
	for(;pos;pos-=lowbit(pos))ans+=ta[pos];
	return ans;
}
int main()
{
	int i;
	scanf("%d%d",&N,&M);
	for(i=1;i<=N;i++)scanf("%d",a+i),tmp[++tot]=a[i];
	for(i=1;i<=M;i++)
	{
		scanf("%d%d",q[i],q[i]+1);
		if(q[i][0]==2)scanf("%d",q[i]+2),tmp[++tot]=q[i][2];
		tmp[++tot]=q[i][1];
	}
	sort(tmp+1,tmp+tot+1);
	for(i=1;i<=N;i++)add(a[i]=ls(a[i]),1);
	for(i=2;i<=N;i++)add(min(a[i],a[i-1]),-1);
	for(i=1;i<=M;i++)
	{
		if(q[i][0]==1)
		{
			printf("%d\n",1-sum(ls(q[i][1])-1));
		}
		else
		{
			q[i][2]=ls(q[i][2]);
			add(a[q[i][1]],-1);add(q[i][2],+1);
			if(q[i][1]!=1)
				add(min(a[q[i][1]],a[q[i][1]-1]),+1),
				add(min(q[i][2],a[q[i][1]-1]),-1);
			if(q[i][1]!=N)
				add(min(a[q[i][1]],a[q[i][1]+1]),+1),
				add(min(q[i][2],a[q[i][1]+1]),-1);
			a[q[i][1]]=q[i][2];
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#define N 400005
using namespace std;
int n,m,k,s,t,a[N],b[N],c[N],q[N][3],tot;
int ls(int x){
	return lower_bound(b+1,b+tot+1,x)-b;
}
void add(int x, int v){
	for (int i=x;i<=tot;i+=i&(-i)) c[i]+=v;
}
int query(int x)
{
	int ans=0;
	for (int i=x;i;i-=i&(-i)) ans+=c[i];
	return ans;
}
int main()
{
	freopen("in.txt","r",stdin);
	cin>>n>>m;
	for (int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
	tot=n;
	for (int i=1;i<=m;++i){
		cin>>q[i][0];
		if (q[i][0]==1) cin>>q[i][1];
		else {
			cin>>q[i][1]>>q[i][2];
			b[++tot]=q[i][2];
		}
	}
	b[++tot]=0;//把0也离散了 
	sort(b+1,b+1+tot);
	for (int i=0;i<=n+1;++i) a[i]=ls(a[i]);
	for (int i=0;i<=n;++i) {//更新树状数组 
		add(max(a[i],a[i+1]),1);
		add(min(a[i],a[i+1]),-1);
	}
	for (int i=1;i<=m;++i)
		if (q[i][0]==1) cout<<(query(tot)-query(ls(q[i][1])-1))/2<<"\n";
		else {
			int x=q[i][1]; 
			add(max(a[x-1],a[x]),-1);add(min(a[x-1],a[x]),1);
			add(max(a[x+1],a[x]),-1);add(min(a[x+1],a[x]),1);
			//还原 
			a[x]=ls(q[i][2]);//修改a[x] 
			add(max(a[x-1],a[x]),1);add(min(a[x-1],a[x]),-1);
			add(max(a[x+1],a[x]),1);add(min(a[x+1],a[x]),-1);
			//更新 
		}
}

暑假的救赎day2

#include <bits/stdc++.h>
using namespace std;
int n,m,a[200005],c[400005],ls[400005],op[200005],k1[200005],y[200005],pos;//ls,c数组长度要翻倍 
int lsh(int id)//这里的id要是真实的值，因为 67行那个不是a数组的id 
{
	return lower_bound(ls+1,ls+pos+1,id) - ls;//离散数组长度为pos 
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int k)
{
	for(;x <= pos;x += lowbit(x))
	{
		c[x] += k;
	}
/*	for(int i=1; i <= 10; i++)
	{
		cout << c[i] << " ";
	}
	cout << endl;*/
}
int sum(int x)
{
	int ans = 0;
	for(; x ; x -= lowbit(x))
	{
		ans += c[x]; 
	}
	return ans;
}
int main()
{
	
	cin >> n >> m;
	for(int i=1; i <= n ;i++)
	{
		cin >> a[i];
		ls[++pos] = a[i];
	}
	a[n+1] = 0;ls[++pos]=0;//把0也离散了，然后把0位置和n+1位置都视为0 
	for(int i=1; i <= m ;i++)
	{
		cin >> op[i];
		if(op[i] == 1)
		{
			cin >> k1[i];
		}
		else
		{
			cin >> k1[i] >> y[i];
			ls[++pos] = y[i];
		}
	}
	sort(ls+1,ls+pos+1);
	for(int i=0; i <= n ;i++)//从0到n 
	{
		add(max(lsh(a[i]),lsh(a[i+1])),1);
		add(min(lsh(a[i]),lsh(a[i+1])),-1);
	}
	for(int i=1; i <= m ; i++)
	{
		if(op[i] == 1)
		{//这里看ppt里的解释 
			cout << sum(pos)-sum(lsh(k1[i])-1) / 2<< endl;
		}
		else
		{//这里有4个要处理，分别是和i-1的maxmin，和i+1的maxmin 
			add(max(lsh(a[k1[i]]),lsh(a[k1[i]+1])),-1);add(min(lsh(a[k1[i]]),lsh(a[k1[i]+1])),+1);
			add(max(lsh(a[k1[i]]),lsh(a[k1[i]-1])),-1);add(min(lsh(a[k1[i]]),lsh(a[k1[i]-1])),+1);
		    a[k1[i]] = y[i];
		    add(max(lsh(a[k1[i]]),lsh(a[k1[i]+1])),1);add(min(lsh(a[k1[i]]),lsh(a[k1[i]+1])),-1);
			add(max(lsh(a[k1[i]]),lsh(a[k1[i]-1])),1);add(min(lsh(a[k1[i]]),lsh(a[k1[i]-1])),-1);
		}
	}
	return 0;
}********

用0表示<水面，1表示>=水面

一个露出的部分类似这样:00011111..1100

假设有n个1，

那么相邻之间max为1的有n+1对，

min为1的有n-1对。

可以发现: (max>=x的 - min>=x的)/2 = x的答案

所以我们对max,min维护一个东西，支持删除，插入，查询>=一个数的个数。

可以离散化+树状数组。

#include<bits/stdc++.h>
using namespace std;

const int N=400100;

int a[N],c[N],top;
void add(int i,int x)
{
    i=top-i+1;
    for(;i<=top;i+=i&-i) c[i]+=x;
}
int qiu(int i)
{
    i=top-i+1;
    int ans=0;
    for(;i;i-=i&-i) ans+=c[i];
    return ans;
}

namespace kcz
{
  int *q[N],tot;
  void push(int *x)
  {
    q[++tot]=x;
  }
  bool xiao(int *x,int *y)
  {
      return *x<*y;
  }
  void lisan()
  {
       sort(q+1,q+tot+1,xiao);
       top=1;
     int now=*q[1];*q[1]=1;
       for(int i=2;i<=tot;++i)
       {
           if(*q[i]!=now) { now=*q[i];++top; }
           *q[i]=top;
       }
  }
};
struct query
{
    int type,i,x;
    void init()
    {
        scanf("%d",&type);
        if(type==1)  scanf("%d",&x); 
        else  scanf("%d%d",&i,&x);
        kcz::push(&x);
    }
    void solve()
    {
        if(type==1)  printf("%d\n",qiu(x)>>1);
        else
        {
            add(max(a[i],a[i+1]),-1);add(min(a[i],a[i+1]),1);
            add(max(a[i],a[i-1]),-1);add(min(a[i],a[i-1]),1);
            a[i]=x;
            add(max(a[i],a[i+1]),1);add(min(a[i],a[i+1]),-1);
            add(max(a[i],a[i-1]),1);add(min(a[i],a[i-1]),-1);
        }
    }
}q[N];

int main()
{ freopen("1.in","r",stdin);
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i) scanf("%d",a+i);
    for(i=0;i<=n+1;++i) kcz::push(a+i);
    for(i=1;i<=m;++i) q[i].init();
    kcz::lisan();
    for(i=0;i<=n;++i) 
    {add(max(a[i],a[i+1]),1);add(min(a[i],a[i+1]),-1);
    }
    for(i=1;i<=m;++i) q[i].solve();
}