#include<bits/stdc++.h>
using namespace std;
int n,m,t,p,b[310000],tr[310000],d[310000],e[310000],g[310000],kk;
char ch[100];
struct sth {
int x,y,z,w,ans;
} a[310000],c[310000];
void add(int x,int y,int op) {
b[++p]=a[++t].x=x;
a[t].y=y;
a[t].z=t;
a[t].w=op;
}
void add(int x,int k) {
while(x<=p) {
tr[x]+=k;
x+=x&(-x);
}
}
int qy(int x) {
int s=0;
while(x) {
s+=tr[x];
x-=x&(-x);
}
return s;
}
void cdq(int l,int r) {
if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
int i=l,j=mid+1,cnt=0,tt=0;
for(; j<=r; j++) {
while(i<=mid&&a[i].y<=a[j].y) {
if(a[i].w==0)add(a[i].x,1),d[++cnt]=a[i].x;
c[++tt]=a[i++];
}
if(a[j].w!=0)a[j].ans+=qy(a[j].x);
c[++tt]=a[j];
}
for(int i=1; i<=cnt; i++)add(d[i],-1);
while(i<=mid)c[++tt]=a[i++];
tt=0;
for(int i=l; i<=r; i++)a[i]=c[++tt];
}
bool cmp(sth a,sth b) {
return a.z<b.z;
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
scanf("%d",&e[i]);
add(i-e[i],i+e[i],0);
}
int cnt=0;
for(int i=1; i<=m; i++) {
int x,y;
scanf("%s",ch+1);
scanf("%d%d",&x,&y);
if(ch[1]=='Q') {
add(x-e[x]+y,e[x]+x+y,1);
g[++cnt]=t;
add(x-e[x]-y-1,e[x]+x-y-1,1);
add(x-e[x]+y,e[x]+x-y-1,-1);
add(x-e[x]-y-1,e[x]+x+y,-1);
} else {
e[x]=y;
add(x-e[x],e[x]+x,0);
}
}
sort(b+1,b+1+p);
kk=unique(b+1,b+1+p)-b-1;
for(int i=1; i<=t; i++)a[i].x=lower_bound(b+1,b+1+kk,a[i].x)-b;
cdq(1,t);
sort(a+1,a+1+t,cmp);
for(int i=1; i<=cnt; i++)printf("%d\n",a[g[i]].ans+a[g[i]+1].ans-a[g[i]+2].ans-a[g[i]+3].ans);
return 0;
}
标签:int,mid,310000,P10633,add,cdq
From: https://www.cnblogs.com/zan-mei-tai-yang/p/18445020