[文章目录]
Description
给定一个长度为n的正整数数列a[i]。
定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。2种操作（k都是正整数）：
1.Modify x k：将第x个数的值修改为k。
2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为同样的数值，按多次统计）
查询的形式为到定点的曼哈顿距离，KD-tree维护矩形内点的个数，修改历史版本看成加点即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,d,rot,a[61000],cg[101000],cgg;
double arf=0.75;
struct KD_tree
{
int p[2],mi[2],mx[2],ls,rs,siz;
void clear()
{
mi[0]=mx[0]=p[0];
mi[1]=mx[1]=p[1];
siz=1; ls=rs=0;
}
}t[101000];
bool operator < (const KD_tree x,const KD_tree y)
{
return x.p[d]==y.p[d] ? x.p[d^1]<y.p[d^1] : x.p[d]<y.p[d];
}
bool cmp(int x,int y){return t[x]<t[y];}
void pushup(int p,int k)
{
t[p].mi[0]=min(t[p].mi[0],t[k].mi[0]);
t[p].mx[0]=max(t[p].mx[0],t[k].mx[0]);
t[p].mi[1]=min(t[p].mi[1],t[k].mi[1]);
t[p].mx[1]=max(t[p].mx[1],t[k].mx[1]);
t[p].siz+=t[k].siz;
}
int build(int l,int r,int fl)
{
int mid=(l+r)>>1; d=fl;
nth_element(cg+l,cg+mid,cg+r+1,cmp);
int re=cg[mid];
if(l<mid) pushup(re,t[re].ls=build(l,mid-1,fl^1));
if(r>mid) pushup(re,t[re].rs=build(mid+1,r,fl^1));
return re;
}
void flatten(int p)
{
if(!p) return ;
flatten(t[p].ls); flatten(t[p].rs);
t[p].clear(); cg[++cgg]=p;
}
void rebuild(int &p,int D)
{
cgg=0; flatten(p);
p=build(1,cgg,D);
}
void insert(int &p,int k,int fl,int D)
{
if(!p) {p=k; return ;}
pushup(p,k); d=D;
if(t[k]<t[p])
{
if(!fl&&t[t[p].ls].siz+1>t[p].siz*arf) insert(t[p].ls,k,1,D^1),rebuild(p,D);
else insert(t[p].ls,k,fl,D^1);
}
else
{
if(!fl&&t[t[p].rs].siz+1>t[p].siz*arf) insert(t[p].rs,k,1,D^1),rebuild(p,D);
else insert(t[p].rs,k,fl,D^1);
}
}
int query(int p,int x,int dx,int y,int dy)
{
if(!p||x>t[p].mx[0]||dx<t[p].mi[0]||y>t[p].mx[1]||dy<t[p].mi[1]) return 0;
if(x<=t[p].mi[0]&&dx>=t[p].mx[0]&&y<=t[p].mi[1]&&dy>=t[p].mx[1]) return t[p].siz;
int re=0;
if(t[p].p[0]>=x&&t[p].p[0]<=dx&&t[p].p[1]>=y&&t[p].p[1]<=dy) re++;
re+=query(t[p].ls,x,dx,y,dy)+query(t[p].rs,x,dx,y,dy);
return re;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",a+i);
t[i].p[0]=i+a[i];
t[i].p[1]=i-a[i];
t[i].clear();
cg[i]=i;
}
rot=build(1,n,0); char sw[10]; int x,k;
while(m--)
{
scanf("%s%d%d",sw,&x,&k);
if(sw[0]=='M')
{
a[x]=k; n++; t[n].p[0]=x+k; t[n].p[1]=x-k; t[n].clear();
insert(rot,n,0,0);
}
else printf("%d\n",query(rot,x+a[x]-k,x+a[x]+k,x-a[x]-k,x-a[x]+k));
}
return 0;
}