传送门
二进制分组入门题。
主席树写错调题2h+2h+2h+体验极差。
题意简述：给一堆点，支持加入一个点，询问有多少个点跟(x,y)(x,y)(x,y)曼哈顿距离不超过kkk。
思路：题目要求的是对于一个斜着的正方形的查询。
我们考虑转切比雪夫距离转成正常的正方形。
然后就变成了一个动态的二维数点问题。
这个时候已经可以上cdqcdqcdq分治+扫描线或者树套树切题啦。
然而还有一种叫做二进制分组的方法可以支持强制在线的操作。
我们考虑将修改分组，例如对于前19=16+2+119=16+2+119=16+2+1个修改操作可以把它拆成第111 ~ 161616个修改操作，第171717~181818个修改操作，第191919个修改操作这三组，每个组分别维护自己的答案，询问就从各个组分别询问之后把答案累加起来。
然后如果现在又来了第202020个操作，就需要把最后两个合并成一组，变成20=16+2+220=16+2+220=16+2+2，接着发现最后两个组都是222，又需要把最后两个合并成一组，变成20=16+420=16+420=16+4。
即我们模拟二进制数的进位来对修改操作进行组与组之间的合并
可以发现这样的时间复杂度是O(nlogn2)O(nlog_n^2)O(nlogn2)的，足以通过所有测试点。
最后提一下合并时候的处理方法：我们暴力删除最后一个组，然后重构倒数第二个组
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=2e5+5,K=1e7+5,lim=2e5,Maxn=100000;
int n,m,a[N],rt[20][N],tp=0;
struct segement_tree{
#define lc (son[p][0])
#define rc (son[p][1])
#define mid (l+r>>1)
int siz[K],son[K][2],stk[K],top;
bool vis[K];
segement_tree(){memset(siz,0,sizeof(siz)),memset(son,0,sizeof(son)),top=0;for(ri i=1;i<K;++i)stk[++top]=i,vis[i]=0;}
inline int newnode(){return vis[stk[top]]=1,stk[top--];}
inline void insert(int&p,int o,int l,int r,int k){
siz[p=newnode()]=siz[o]+1,lc=son[o][0],rc=son[o][1];
if(l==r)return;
k<=mid?insert(lc,son[o][0],l,mid,k):insert(rc,son[o][1],mid+1,r,k);
}
inline int query(int pl,int pr,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return siz[pr]-siz[pl];
if(qr<=mid)return query(son[pl][0],son[pr][0],l,mid,ql,qr);
if(ql>mid)return query(son[pl][1],son[pr][1],mid+1,r,ql,qr);
return query(son[pl][0],son[pr][0],l,mid,ql,qr)+query(son[pl][1],son[pr][1],mid+1,r,ql,qr);
}
inline void delet(int&p){
if(!vis[p])return;
stk[++top]=p,vis[p]=0,delet(lc),delet(rc),siz[p]=0,p=0;
}
}T;
typedef pair<int,int> pii;
vector<pii>v[20];
inline void update(int x,int y){
v[++tp].push_back(pii(x,y));
T.insert(rt[tp][1],rt[tp][0],1,lim,y);
while(tp>1&&v[tp].size()==v[tp-1].size()){
int p1=0,p2=0;
vector<pii>tmp;
for(ri i=1;i<=v[tp].size();++i)T.delet(rt[tp][i]);
for(ri i=1;i<=v[tp-1].size();++i)T.delet(rt[tp-1][i]);
while(p1<v[tp-1].size()||p2<v[tp].size()){
if(p1<v[tp-1].size()&&(p2==v[tp].size()||v[tp-1][p1]<v[tp][p2]))tmp.push_back(v[tp-1][p1++]);
else tmp.push_back(v[tp][p2++]);
T.insert(rt[tp-1][p1+p2],rt[tp-1][p1+p2-1],1,lim,tmp[p1+p2-1].se);
}
v[tp-1]=tmp,v[tp].clear(),--tp;
}
}
inline int query(int x,int y,int k){
int ret=0;
for(ri p1,p2,i=1;i<=tp;++i){
p1=lower_bound(v[i].begin(),v[i].end(),pii(x-k,0))-v[i].begin();
p2=lower_bound(v[i].begin(),v[i].end(),pii(x+k,1e9))-v[i].begin();
ret+=T.query(rt[i][p1],rt[i][p2],1,lim,max(1,y-k),min(lim,y+k));
}
return ret;
}
int main(){
n=read(),m=read();
for(ri i=1;i<=n;++i)a[i]=read(),update(a[i]+i,a[i]-i+Maxn);
for(ri i=1,x,y;i<=m;++i){
char s[2];
scanf("%s",s);
x=read(),y=read();
if(s[0]=='M')a[x]=y,update(a[x]+x,a[x]-x+Maxn);
else cout<<query(a[x]+x,a[x]-x+Maxn,y)<<'\n';
}
return 0;
}