bzoj

该说不愧是咱，一个月才水一篇题解然后还水的一批

题目描述：

给定一个长度为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的对数。（某位置多次修改为

同样的数值，按多次统计）

题解时间：

题目描述等效于先给出n个点之后操作为加一个新点或查询一个斜正方形内的点数

但是如果用kdt查斜正方形的话时间复杂度有被卡的风险。

所以旋转一下坐标系（旋转后的坐标系长什么样都行）

然后就变成查一个正方形了

插点的操作用替罪羊树暴力重构就好。

1 #include
2 #include
3 const int N=100011;
4 using std::max;
5 using std::min;
6 using std::nth_element;
7 template
8 inline void read(TP &_t)
9 {
10 TP _r=0,_f=1;char _c=getchar();
11 while(_c<'0'||_c>'9'){if(_c=='-')_f=-1;_c=getchar();}
12 while(_c>='0'&&_c<='9'){_r=_r*10+_c-'0';_c=getchar();} 13 _t=_r*_f; 14 } 15 int n,T; 16 struct poi 17 { 18 int x[2]; 19 poi(){} 20 poi(int a,int b){x[0]=a,x[1]=b;} 21 }; 22 int DD; 23 int rt; 24 int lbx,lby,rtx,rty; 25 struct shion 26 { 27 int son[2],x[2],ma[2],mi[2],size,id; 28 }p[N]; 29 int pi; 30 bool cmp(int a,int b){return p[a].x[DD]==p[b].x[DD]?p[a].x[!DD]p[px].size*70)
60 ux=px,uf=(f?(&p[f].son[p[f].son[1]==px]):(&rt)),unbalance=1,ud=dim;
61 if(p[px].son[1]&&p[p[px].son[1]].size*100>p[px].size*70)
62 ux=px,uf=(f?(&p[f].son[p[f].son[1]==px]):(&rt)),unbalance=1,ud=dim;
63 }
64 void rebuild();
65 void insert(poi a)
66 {
67 insert(rt,a,0);
68 if(unbalance) rebuild();
69 }
70 int ul[N],uli;
71 void dfs(int px)
72 {
73 if(!px) return;
74 dfs(p[px].son[0]);
75 ul[++uli]=px;
76 dfs(p[px].son[1]);
77 p[px].son[0]=p[px].son[1]=0;
78 }
79 void build(int &px,int l,int r,int dim)
80 {
81 if(l==r)
82 {
83 px=ul[l];
84 fuckup(px);
85 return;
86 }
87 DD=dim;
88 int pm=l+r>>1;
89 nth_element(ul+l,ul+pm,ul+r+1,cmp);
90 px=ul[pm];
91 if(lpm) build(p[px].son[1],pm+1,r,dim^1);
93 fuckup(px);
94 }
95 void rebuild()
96 {
97 uli=0;
98 dfs(ux);
99 *uf=0;
100 build(*uf,1,uli,ud);
101 unbalance=0;
102 }
103 int check(int px)
104 {
105 if(p[px].ma[0]rtx||p[px].ma[1]rty) return -1;
106 if(lbx<=p[px].mi[0]&&p[px].ma[0]<=rtx&&lby<=p[px].mi[1]&&p[px].ma[1]<=rty) return 1;
107 return 0;
108 }
109 int query(int px)
110 {
111 if(!px) return 0;
112 int pas=check(px);
113 switch(pas)
114 {
115 case -1:{
116 return 0;
117 break;
118 }
119 case 0:{
120 return query(p[px].son[0])+query(p[px].son[1])+(lbx<=p[px].x[0]&&p[px].x[0]<=rtx&&lby<=p[px].x[1]&&p[px].x[1]<=rty);
121 break;
122 }
123 case 1:{
124 return p[px].size;
125 break;
126 }
127 }
128 }
129 int a[N];
130
131 int xi,yi;
132 char op[5];
133 int main()
134 {
135 for(int i=1;i<=100000;i++) p[i].id=i;
136 read(n),read(T);
137 for(int i=1;i<=n;i++) read(a[i]),
138 insert(poi(i+a[i],i-a[i]));
139 while(T--)
140 {
141 scanf("%s",op);
142 switch(op[0])
143 {
144 case 'M':
145 {
146 read(xi),read(yi);
147 insert(poi(xi+yi,xi-yi));
148 a[xi]=yi;
149 break;
150 }
151 case 'Q':
152 {
153 read(xi),read(yi);
154 lbx=xi+a[xi]-yi,lby=xi-a[xi]-yi;
155 rtx=xi+a[xi]+yi,rty=xi-a[xi]+yi;
156 printf("%d\n",query(rt));
157 break;
158 }
159 }
160 }
161 return 0;
162 }

(数据删除)被数据结构的装腔作势激怒了