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的对数。（某位置多次修改为同样的数值，按多次统计）

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 询问<=60000 Max{a[i]}含修改<=100000

Solution

这道题其实是维护两种操作，向平面上加点，查询菱形内点数
把(x,y)变为(x+y,x-y)，菱形就变成了正方形
假设某个询问是以(x0,y0)为中心，边长为2k的正方形，那么可以拆成两个，一个是x>=x0-k且x<=x0+k且y<=y0+k的点数，另一个是x>=x0-k且x<=x0+k且y<y0-k的点数，把两个询问做差就和原询问相同
那么可以CDQ分治，按y排序，x用树状数组维护

Code

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. int n,m,s[60001],ans[60000],ac,qc,mx;
  7. struct query
  8. {
  9.     int x,y,k,id;char op;
  10. }q[230000],tmp[230000];
  12. inline void add(int x,int y){q[qc].x=x+y,q[qc].y=x-y,qc++,mx=max(mx,x+y);}
  14. int p[160001];
  15. inline void pl(int x){for(;x<=mx;x+=x&-x)p[x]++;}
  16. inline int qr(int x){if(x<=0)return 0;int r=0;for(x=min(x,mx);x;x^=x&-x)r+=p[x];return r;}
  17. inline void cl(int x){for(;x<=mx;x+=x&-x)p[x]=0;}
  19. void work(int l,int r)
  20. {
  21.     if(l==r)return;
  22.     int mid=(l+r)>>1;
  23.     work(l,mid),work(mid+1,r);
  24.     int i1=l,i2=mid+1,ti=l;
  25.     for(;i2<=r;tmp[ti++]=q[i2++])
  26.     {
  27.         for(;i1<=mid&&q[i1].y<=q[i2].y;tmp[ti++]=q[i1++])
  28.             if(!q[i1].op)pl(q[i1].x);
  29.         if(q[i2].op)
  30.         {
  31.             if(q[i2].op==1)
  32.                 ans[q[i2].id]+=qr(q[i2].x+q[i2].k)-qr(q[i2].x-q[i2].k-1);
  33.             else
  34.                 ans[q[i2].id]+=qr(q[i2].x-q[i2].k-1)-qr(q[i2].x+q[i2].k);
  35.         }
  36.     }
  37.     for(;i1<=mid;tmp[ti++]=q[i1++]);
  38.     for(i1=l;i1<=mid;i1++)if(!q[i1].op)cl(q[i1].x);
  39.     for(i1=l;i1<=r;i1++)q[i1]=tmp[i1];
  40. }
  42. int main()
  43. {
  44.     scanf("%d%d",&n,&m);
  45.     for(int i=1;i<=n;i++)
  46.         scanf("%d",s+i),add(i,s[i]);
  47.     char tmp[10];int a,b;
  48.     while(m--)
  49.     {
  50.         scanf("%s%d%d",tmp,&a,&b);
  51.         if(tmp[0]=='M')
  52.             add(a,s[a]=b);
  53.         else
  54.         {
  55.             int x=a+s[a],y=a-s[a];
  56.             q[qc].x=x,q[qc].y=y+b,q[qc].k=b,q[qc].id=ac,q[qc].op=1,qc++;
  57.             q[qc].x=x,q[qc].y=y-b-1,q[qc].k=b,q[qc].id=ac,q[qc].op=2,qc++;
  58.             ac++;
  59.         }
  60.     }
  61.     work(0,qc-1);
  62.     for(int i=0;i<ac;i++)
  63.         printf("%d\n",ans[i]);
  64. }