给定一个长度为n的正整数数列a[i]。
定义2个位置的f值为两者位置差与数值差的和，即f(x,y)=|x-y|+|a[x]-a[y]|。
你需要写一个程序支持2种操作（k都是正整数）：
Modify x k：将第x个数的值修改为k。
Query x k：询问有几个i满足f(x,i)<=k。询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的f值<=k的对数。（某位置多次修改为同样的数值，按多次统计）
也许可以cdq分治时间+树状数组搞一维坐标+线段树维护和，时间复杂度 O(n log3n)
然而曼哈顿距离在k以内的点其实在一个菱形内的。
旋转45°就变成了矩形，这样就可以上数据结构了。
（x,y）变成(x-y,x+y)注意这里是乘上了 2√ 以后的坐标，直接旋转45°的话因为sin45=cos45= 12√ 。 这样搞一下曼哈顿距离就变成了雪顿距离。
利用带修主席树搞矩阵内点数就行了。
Code：
#include<cmath> #include<cstdio> #include<cstring> #define fo(i, x, y) for(int i = x; i <= y; i ++) #define low(x) ((x) & -(x)) #define min(a, b) ((a) < (b) ? (a) : (b)) using namespace std; const int N = 1e5 + 5, M = 120000; char str[10]; int n, Q, a[N]; int x, y, k, z; int tt, s[N * 300], l[N * 300], r[N * 300]; struct tree { int rt, pl, pr; void dg(int &i, int x, int y) { if(y < pl || x > pl) return; if(!i) i = ++ tt; if(x == y) {s[i] ++; return;} int m = x + y >> 1; dg(l[i], x, m); dg(r[i], m + 1, y); s[i] = s[l[i]] + s[r[i]]; } void add(int x) {pl = x; dg(rt, -M, M);} int dd(int &i, int x, int y) { if(y < pl || x > pr || !i) return 0; if(x >= pl && y <= pr) return s[i]; int m = x + y >> 1; return dd(l[i], x, m) + dd(r[i], m + 1, y); } int fi(int x, int y) { pl = x; pr = y; return dd(rt, -M, M); } } t[M + 5]; void GG(int x, int y) { int z = x; x -= y; y += z; while(y <= M) t[y].add(x), y += low(y); } int ff(int x, int y) { if(x < -M || y < 0) return 0; x = min(x, M); y = min(y, M); int s = 0; while(y) s += t[y].fi(-M, x), y -= low(y); return s; } int main() { scanf("%d %d", &n, &Q); fo(i, 1, n) scanf("%d", &a[i]), GG(i, a[i]); for(; Q; Q --) { scanf("%s", str + 1); if(str[1] == 'Q') { scanf("%d %d", &z, &k); x = z; y = a[z]; x -= y; y += z; printf("%d\n", ff(x + k, y + k) - ff(x - k - 1, y + k) - ff(x + k, y - k - 1) + ff(x - k - 1, y - k - 1)); } else { scanf("%d %d", &x, &y); GG(x, y); a[x] = y; } } }