题目描述
给定一个长度为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的对数。（某位置多次修改为
同样的数值，按多次统计）
输入
第1行两个整数n,q。分别表示数列长度和操作数。
第2行n个正整数，代表初始数列。
第3--q+2行每行一个操作。
输出
对于每次询问操作，输出一个非负整数表示答案
样例输入
3 5 2 4 3 Query 2 2 Modify 1 3 Query 2 2 Modify 1 2 Query 1 1
样例输出
2 3 3
题解
KD-tree+旋转坐标系
这里的“可持久化”是逗你玩的，实际上操作只有两种：在平面上加一个点、在平面上查询到一个点曼哈顿距离不超过k的点的个数。
KD-tree就可以搞，然而这样做会TLE，因为查询斜正方形时间复杂度无法保证。
所以考虑把所有的点绕着原点逆时针旋转45度，查询的就是一个矩形空间，就可以直接使用KD-tree。
根据数学知识可知点$(x,y)$旋转后变为点$(\frac{x-y}{\sqrt 2},\frac{x+y}{\sqrt 2})$，可以把所有的$\sqrt 2$约掉，变为$(x-y,x+y)$。
查询时查的就是与某点切比雪夫距离不超过k（一个正方形范围）的点的个数。
亲测不加重构跑得比加重构还快，所以不用加了。
#include#include #include #include #define N 100010using namespace std;int d , root , g[N];char str[10];struct data{ int p[2] , mx[2] , mn[2] , sum , c[2]; bool operator<(data a)const {return p[d] == a.p[d] ? p[d ^ 1]< a.p[d ^ 1] : p[d] < a.p[d];}}a[N];void pushup(int x){ int l = a[x].c[0] , r = a[x].c[1]; a[x].mx[0] = max(a[x].p[0] , max(a[l].mx[0] , a[r].mx[0])); a[x].mx[1] = max(a[x].p[1] , max(a[l].mx[1] , a[r].mx[1])); a[x].mn[0] = min(a[x].p[0] , min(a[l].mn[0] , a[r].mn[0])); a[x].mn[1] = min(a[x].p[1] , min(a[l].mn[1] , a[r].mn[1])); a[x].sum = a[l].sum + a[r].sum + 1;}int build(int l , int r , int now){ int mid = (l + r) >> 1; d = now , nth_element(a + l , a + mid , a + r + 1); a[mid].c[0] = a[mid].c[1] = 0; if(l < mid) a[mid].c[0] = build(l , mid - 1 , now ^ 1); if(r > mid) 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[x] < a[k]) d ^= 1 , insert(a[k].c[0] , x); else d ^= 1 , insert(a[k].c[1] , x); pushup(k);}int judge(int k , int x1 , int y1 , int x2 , int y2){ if(!k || a[k].mx[0] < x1 || a[k].mx[1] < y1 || a[k].mn[0] > x2 || a[k].mn[1] > y2) return -1; if(a[k].mn[0] >= x1 && a[k].mn[1] >= y1 && a[k].mx[0] <= x2 && a[k].mx[1] <= y2) return 1; return 0;}int query(int k , int x1 , int y1 , int x2 , int y2){ int tmp = judge(k , x1 , y1 , x2 , y2); if(tmp == 1) return a[k].sum; if(tmp == -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(){ a[0].mx[0] = a[0].mx[1] = -1 << 30 , a[0].mn[0] = a[0].mn[1] = 1 << 30; int n , m , i , x , y; scanf("%d%d" , &n , &m); for(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(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;}