很有意思的一道题，来水一篇：
-
Analysis:
首先，我们对于每一个连通块，都需要找到一个特征值来统计，思考一下就知道它是每个连通块的左或右端点，本文使用左端点来统计。
进而，我们考虑对于每一种高度的答案分开统计，我们用 \(0\) 代表在当前高度下露出水面的石柱，用 \(1\) 表示当前高度下被水淹没的石柱，然后我们思考以下情况：
约定：\(H_i\) 轴代表高度，\(X_i\) 轴表示石柱：
\[\begin{matrix} H_6(0)&&0&0&0&0&0\\ H_5(1)&&0&0&1&0&0\\ H_4(1)&&0&0&1&1&1\\ H_3(2)&&1&0&1&1&1\\ H_2(1)&&1&1&1&1&1\\ H_1(1)&&1&1&1&1&1\\\\ &&X_1&X_2&X_3&X_4&X_5 \end{matrix}\]我们考虑修改操作：对于 \(X_i\) ，它的降低显然会对降低后对应的答案造成贡献，具体来说：当石柱 \(X_i\) 降低时，我们分别考虑所有会变化的值（答案），如果当前 \(H\) 下，减少的那个石柱的左右两边为空，则当前高度下连通块的数量减少 \(1\)，否则就增加 \(1\)，我们不妨手玩一下：
假设当前 \(X_3\) 减少到了 \(H_1\) 那么原图转化为：
\[\begin{matrix} H_6(0)&&0&0&0&0&0\\ H_5(1-1)&&0&0&0&0&0\\ H_4(1)&&0&0&0&1&1\\ H_3(2)&&1&0&0&1&1\\ H_2(1+1)&&1&1&0&1&1\\ H_1(1)&&1&1&1&1&1\\\\ &&X_1&X_2&X_3&X_4&X_5 \end{matrix}\]我们发现：二维点对 \((X_3,H_5)\) 两边均无石柱，因此 \(H_5\) 中的贡献减一为零，而 \((X_3,H_2)\) 的两边均有石柱，因此 \(H_2\) 中的贡献加一为二。\((X_3,H_3)\) 与 \((X_3,H_4)\) 两边一边有石柱，一边没有，那么修改就对当前答案无贡献，因此 \(H_3\) 与 \(H_4\) 不变。
到此我们已经找到了规律，我们很容易将其推广到石柱上升时的情况，那么对于以上修改时的三种情况：两边均有，两边均无，一边有一边无。我们就可以分讨实现修改了。
-
Achieve：
数据结构维护一下我们上文提到的 \(H_i\)，既然是高度，当然要离散化。然后，根据上面的手模，每次的答案更新不同，很麻烦，如何避免？我们考虑每次在修改前，将本次修改影响的答案区间贡献减一，再正常操作，不明白？我们再来手玩一下：
还是上面我们提到的情况：将 \(X_3\) 降低至 \(H_1\)，因为修改之前 \(X_2\)的高度 小于 \(X_3\)，所以我们先将 \(H_{2+1}\) 即 \(H_3\) 到 \(H_5\) 的区间减一消除影响，再将 \(X_3\) 修改至 \(H_1\) 高度，此时 \(X_3\) 的高度小于 \(X_4\)，能产生新的左端点，因此 \(H_{1+1}\) 即 \(H_2\) 到 \(H_4\) 答案区间加一。至此，\(H_3\) 和 \(H_4\) 的影响抵消，我们完成了想要实现的修改操作。
至于为什么区间修改时，要将左高度加一，这是因为本文选用左端点统计答案，做高度本身就能成为一个左端点。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=400005;
struct node{
int h,id;
bool operator <(const node &b)const
{return h<b.h;}
}a[N<<1];
int h[N<<1],x[N<<1],k[N<<1];
int n,m,mx;
namespace TREE{
int dat[N<<2],tag[N<<2];
void pushdown(int pos){
if(!tag[pos]) return;
int lson=pos<<1,rson=pos<<1|1;
dat[lson]+=tag[pos],dat[rson]+=tag[pos];
tag[lson]+=tag[pos],tag[rson]+=tag[pos];
tag[pos]=0;
}
void modify(int pos,int l,int r,int ql,int qr,int x){
if(ql<=l&&qr>=r){
dat[pos]+=x,tag[pos]+=x;return;
}
pushdown(pos);
int mid=(l+r)>>1;
if(ql<=mid) modify(pos<<1,l,mid,ql,qr,x);
if(qr>mid) modify(pos<<1|1,mid+1,r,ql,qr,x);
}
int query(int pos,int l,int r,int x){
if(l==r) return dat[pos];
pushdown(pos);
int mid=(l+r)>>1;
if(x<=mid) return query(pos<<1,l,mid,x);
else return query(pos<<1|1,mid+1,r,x);
}
}
int main(){
freopen("darkteam.in","r",stdin);
freopen("darkteam.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i].h),a[i].id=i;
for(int i=n+1;i<=n+m;++i){
scanf("%d",&k[i]);
if(k[i]==2) scanf("%d",&x[i]);
scanf("%d",&a[i].h);
a[i].id=i;
}
sort(a+1,a+1+n+m);
h[a[1].id]=1;
for(int i=2;i<=n+m;++i) h[a[i].id]=a[i].h>a[i-1].h?h[a[i-1].id]+1:h[a[i-1].id];
mx=h[a[n+m].id];
for(int i=1;i<=n;++i) if(h[i-1]<h[i]) TREE::modify(1,1,mx,h[i-1]+1,h[i],1);
for(int i=n+1;i<=n+m;++i){
if(k[i]==2){
int t=x[i];
if(h[t-1]<h[t]) TREE::modify(1,1,mx,h[t-1]+1,h[t],-1);
if(t!=n&&h[t]<h[t+1]) TREE::modify(1,1,mx,h[t]+1,h[t+1],-1);
h[t]=h[i];
if(h[t-1]<h[t]) TREE::modify(1,1,mx,h[t-1]+1,h[t],1);
if(t!=n&&h[t]<h[t+1]) TREE::modify(1,1,mx,h[t]+1,h[t+1],1);
}
else printf("%d\n",TREE::query(1,1,mx,h[i]));
}
return 0;
}