233
- 题意：
- 分析：
- 代码：
题意：
我们需要维护两个东西，一个是单点修改高度，另一个是计算大于等于指定高度的连通块的个数
分析：
我们稍微转换下题意，答案所求转换为单个点大于等于hhh的个数?-?相邻两点都大于等于hhh的个数
个数可以通过树状数组愉快维护
代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#define LL long long
#define lowbit(x) (x&(-x))
using namespace std;
inline LL read() {
LL d=0,f=1;char s=getchar();while(s<'0'||s>'9'){
if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){
d=d*10+s-'0';s=getchar();}return d*f;
}
int t[2][500500],a[500500];
void add(int o,int x,int w)
{
while(x<=500100){
t[o][x]+=w;x+=lowbit(x);}return;
}
int query(int o,int x)
{
int sum=0;while(x>0){
sum+=t[o][x];x-=lowbit(x);}return sum;
}
int main()
{
// freopen("patrick.in","r",stdin);
// freopen("patrick.out","w",stdout);int n=read(),m=read();for(int i=1;i<=n;i++) {
a[i]=read()+1;add(0,a[i],1);if(i>1) add(1,min(a[i],a[i-1]),1);}int last=0;for(int i=1;i<=m;i++){
char c;c=getchar();while(c!='Q'&&c!='C') c=getchar();if(c=='Q'){
int h=read()^last;printf("%d\n",last=(query(1,h)-query(0,h)+1));}if(c=='C'){
int x=read()^last,y=(read()^last)+1;add(0,a[x],-1);if(x>1) add(1,min(a[x],a[x-1]),-1);if(x<n) add(1,min(a[x],a[x+1]),-1);add(0,y,1);if(x>1) add(1,min(y,a[x-1]),1);if(x<n) add(1,min(y,a[x+1]),1);a[x]=y;}}return 0;
}