题目
Description
给定一个长度为n的正整数数列a[i]。
定义2个位置的graze值为两者位置差与数值差的和，即$graze(x,y)=\vert x-y\vert +\vert a[x]-a[y]\vert$。
2种操作（k都是正整数）：
1.Modify x k：将第x个数的值修改为k。
2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要
考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为同样的数值，按多次统计）
Input
第1行两个整数n,q。分别表示数列长度和操作数。
第2行n个正整数，代表初始数列。
第3–q+2行每行一个操作。
Output
对于每次询问操作，输出一个非负整数表示答案
Sample Input
3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1
Sample Output
2
3
3
HINT
N<=60000 修改操作数<=40000 询问<=50000 Max{a[i]}含修改<=100000
题解
如果把$a$看成$y$坐标的话就是求二维平面距离某个点曼哈顿距离不超过$k$的共有多少个点
曼哈顿距离是可以转换成切比雪夫距离的
然后就成了支持加入一个点和统计一个矩形内点的个数
$K-D$ $Tree$往上套就行了
三维K-D Tree你是在逗我吗
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
using namespace std;
const int MAX=1e5+5;
const double aph=0.75;
int n,Q,D,Top,tot,rt;
int st[MAX],a[MAX];
struct KD_Tree{
int l,r,siz;
int d[2],mx[2],mi[2];
void add(int x,int y) {d[0]=mx[0]=mi[0]=x,d[1]=mx[1]=mi[1]=y,l=r=0,siz=1;}
bool operator< (const KD_Tree &a)
const{
if(d[D]!=a.d[D]) return d[D]<a.d[D];
return d[D^1]<a.d[D^1];
}
}s[MAX],s1[MAX];
char A[10];
int max(int x,int y) {return x>y?x:y;}
int min(int x,int y) {return x<y?x:y;}
int GET_POINT()
{
if(Top) return st[Top--];
return ++tot;
}
void pus(int k)
{
s[k].siz=s[tl].siz+s[tr].siz+1,s[k].mx[0]=s[k].mi[0]=s[k].d[0],s[k].mx[1]=s[k].mi[1]=s[k].d[1];
if(tl) s[k].mx[0]=max(s[k].mx[0],s[tl].mx[0]),s[k].mi[0]=min(s[k].mi[0],s[tl].mi[0]),s[k].mx[1]=max(s[k].mx[1],s[tl].mx[1]),s[k].mi[1]=min(s[k].mi[1],s[tl].mi[1]);
if(tr) s[k].mx[0]=max(s[k].mx[0],s[tr].mx[0]),s[k].mi[0]=min(s[k].mi[0],s[tr].mi[0]),s[k].mx[1]=max(s[k].mx[1],s[tr].mx[1]),s[k].mi[1]=min(s[k].mi[1],s[tr].mi[1]);
}
int build(int l=1,int r=n,bool d=0)
{
if(l>r) return 0;
int k=GET_POINT();
return D=d,nth_element(s1+l,s1+mid,s1+1+r),s[k]=s1[mid],s[k].siz=1,tl=build(l,mid-1,d^1),tr=build(mid+1,r,d^1),pus(k),k;
}
void dfs(int k,int siz=1)
{
if(tl) dfs(tl,siz);
s1[siz+s[tl].siz]=s[k],st[++Top]=k;
if(tr) dfs(tr,siz+s[tl].siz+1);
}
void look(int &k,bool D) {if(double(s[tl].siz)>aph*s[k].siz||double(s[tr].siz)>aph*s[k].siz) dfs(k),k=build(1,s[k].siz,D);}
void add(int &k,int x,bool D=0)
{
if(!k) return void(k=x);
if(s[x].d[D]<=s[k].d[D]) add(tl,x,D^1);
else add(tr,x,D^1);
pus(k),look(k,D);
}
int ask(int x,int y,int _x,int _y,int k)
{
if(!k) return 0;
if(x<=s[k].mi[0]&&y<=s[k].mi[1]&&_x>=s[k].mx[0]&&_y>=s[k].mx[1]) return s[k].siz;
if(x>s[k].mx[0]||_x<s[k].mi[0]||y>s[k].mx[1]||_y<s[k].mi[1]) return 0;
return (x<=s[k].d[0]&&y<=s[k].d[1]&&_x>=s[k].d[0]&&_y>=s[k].d[1])+ask(x,y,_x,_y,tl)+ask(x,y,_x,_y,tr);
}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read(),Q=read();
for(int i=1,x,_x,y;i<=n;++i)
_x=i,a[i]=y=read(),x=_x+y,y=_x-y,s1[i].add(x,y);
rt=build();
for(int i=1,x,y,_x,_y,k;i<=Q;++i)
{
scanf("%s",A),_x=read(),_y=y=read();
if(A[0]=='Q') y=a[_x],x=_x+y,y=_x-y,printf("%d\n",ask(x-_y,y-_y,x+_y,y+_y,rt));
else if(A[0]=='M') a[_x]=y,x=_x+y,y=_x-y,k=GET_POINT(),s[k].add(x,y),add(rt,k);
}
return 0;
}
