首先考虑没有修改怎么做。
两种做法。
想到询问的形式为保留 \(\ge k\) 的连通块个数，那么先将全部数字按照权值排序，然后从后往前做一遍并查集，并同时统计连通块的数量，在询问时只需二分找到第一个 \(\ge k\) 的位置，将这个位置的答案输出即可。注意考虑答案为 \(0\) 的情况。
但是显然，上面的做法是很难拓展为有修改的情况的，所以这是就要提到另一种做法。
考虑对于一个 \(k\)，哪些情况下会产生新的连通块，显然当 \(a_{i+1}\ge k\) 且 \(a_{i}< k\) 时，在 \(i\) 和 \(i+1\) 之间会断开，产生新的连通块。如果考虑对于一个答案，有多少种这样的情况，由于 \(k\) 会变，所以我们不得不在 \(O(n)\) 遍历一遍，总时间复杂度是 \(O(nm)\)。
考虑对于一种情况，会对多少种答案产生贡献，显然，若 \(a_{i}<a_{i+1}\)，那么，当 \(k\in [a_{i}+1,a_{i+1}]\)，该种情况都会对所有 \(k\) 产生 \(1\) 的贡献。询问时将对应的 \(ans_k\) 输出即可。这是一个区间加，单点查的操作，前缀和+差分即可。
如果加上修改操作，那么对于一个位置上的 \(x\)，将其换成 \(x'\)，只需将之前的贡献消除，将新的贡献加上即可。区间修单点查，容易想到树状数组。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
return sum*flag;
}
const int N=5e5+10,M=5e5;
int n,m;
int tr[N];
int a[N];
int lowbit(int x) {
return x&(-x);
}
void change(int nd,int x) {
for(int i=nd;i<=M;i+=lowbit(i)) tr[i]+=x;
}
int query(int nd) {
int sum=0;
for(int i=nd;i>=1;i-=lowbit(i)) sum+=tr[i];
return sum;
}
void add(int l,int r,int x) {
change(l,x);
change(r+1,-x);
}
int main() {
n=read(); m=read();
for(int i=1;i<=n;i++) {
a[i]=read();
if(a[i-1]<a[i]) add(a[i-1]+1,a[i],1);
}
int lst=0;
while(m--) {
string opt; int x,y;
cin>>opt;
if(opt=="Q") {
x=read(); x^=lst;
lst=query(x);
cout<<lst<<'\n';
}
else {
x=read(); y=read();
x^=lst; y^=lst;
if(a[x-1]<a[x]) add(a[x-1]+1,a[x],-1);
if(a[x]<a[x+1]) add(a[x]+1,a[x+1],-1);
a[x]=y;
if(a[x-1]<a[x]) add(a[x-1]+1,a[x],1);
if(a[x]<a[x+1]) add(a[x]+1,a[x+1],1);
}
}
return 0;
}