[bzoj2989]数列_KD-Tree_旋转坐标系

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
int d,root,g[N];
struct Node
{
	int c[2],minn[2],p[2],maxn[2],sum;
}a[N];
inline void pushup(int x)
{
	int ls=a[x].c[0],rs=a[x].c[1];
	a[x].minn[0]=min(a[x].p[0],min(a[ls].minn[0],a[rs].minn[0]));
	a[x].minn[1]=min(a[x].p[1],min(a[ls].minn[1],a[rs].minn[1]));
	a[x].maxn[0]=max(a[x].p[0],max(a[ls].maxn[0],a[rs].maxn[0]));
	a[x].maxn[1]=max(a[x].p[1],max(a[ls].maxn[1],a[rs].maxn[1]));
	a[x].sum=a[ls].sum+a[rs].sum+1;
}
inline bool cmp(const Node &a,const Node &b)
{
	return a.p[d]==b.p[d]?a.p[d^1]<b.p[d^1]:a.p[d]<b.p[d];
}
int build(int l,int r,int now)
{
	int mid=(l+r)>>1;
	d=now; nth_element(a+l,a+mid,a+r+1,cmp);
	a[mid].minn[0]=a[mid].maxn[0]=a[mid].p[0];
	a[mid].minn[1]=a[mid].maxn[1]=a[mid].p[1];
	a[mid].c[0]=a[mid].c[1]=0;
	if(l<mid) a[mid].c[0]=build(l,mid-1,now^1);
	if(mid<r) a[mid].c[1]=build(mid+1,r,now^1);
	pushup(mid);
	return mid;
}
void insert(int &k , int x)
{
	if(!k) k=x;
	else if(a[k].p[d]<a[x].p[d]||(a[k].p[d]==a[x].p[d]&&a[k].p[d^1]<a[x].p[d^1])) d^=1,insert(a[k].c[0],x);
	else d^=1,insert(a[k].c[1],x);
	pushup(k);
}
inline int judge(int k,int x1,int y1,int x2,int y2)
{
	if(!k||a[k].maxn[0]<x1||a[k].maxn[1]<y1||a[k].minn[0]>x2||a[k].minn[1]>y2) return -1;
	if(a[k].minn[0]>=x1&&a[k].maxn[0]<=x2&&a[k].minn[1]>=y1&&a[k].maxn[1]<=y2) return 1;
	return 0;
}
int query(int k,int x1,int y1,int x2,int y2)
{
	int opt=judge(k,x1,y1,x2,y2);
	if(opt==1) return a[k].sum;
	if(opt==-1) return 0;
	int ans=(a[k].p[0]>=x1&&a[k].p[1]>=y1&&a[k].p[0]<=x2&&a[k].p[1]<=y2);
	return ans+query(a[k].c[0],x1,y1,x2,y2)+query(a[k].c[1],x1,y1,x2,y2);
}
int main()
{
	char str[10];
	a[0].maxn[0]=a[0].maxn[1]=-1<<30,a[0].minn[0]=a[0].minn[1]=1<<30;
	int n,m,x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&g[i]),a[i].p[0]=i-g[i],a[i].p[1]=i+g[i];
	root=build(1,n,0);
	for(int i=1;i<=m;i++)
	{
		scanf("%s%d%d",str,&x,&y);
		if(str[0]=='M')g[x]=y,a[++n].p[0]=x-y,a[n].p[1]=x+y,insert(root,n);
		else printf("%d\n",query(root,x-g[x]-y,x+g[x]-y,x-g[x]+y,x+g[x]+y));
	}
	return 0;
}