题目链接

题面

题意

把每个位置的点都看成是一个二维坐标系中的点。比如第(i)个点就是((i,a[i]))。
有两种操作
询问:然后每次询问的就是与当前点坐标的曼哈顿距离小于等于(k)的点。
修改:修改第i个点的纵坐标。保留历史点。

思路

旋转坐标系。然后就变成了添加一个点和询问一个子矩阵内点的个数。用(cdq)分治或者其他数据结构做就行了

代码

/* * @author: wxyww * @date:   2019-02-15 08:38:47 * @last modified time: 2019-02-15 10:16:11 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 4000010,m = 3000003,bl = 1000000; #define  pi pair<int,int> ll read() {     ll x=0,f=1;char c=getchar();     while(c<'0'||c>'9') {         if(c=='-') f=-1;         c=getchar();     }     while(c>='0'&&c<='9') {         x=x*10+c-'0';         c=getchar();     }     return x*f; } struct node {     int x,y,opt,pos,val; }a[m]; char s[10]; int tt[n],tot; int tree[m],mx,ans[n]; vector<pi>v; void update(int pos,int c) {     while(pos <= bl*3) {         tree[pos] += c;         pos += pos & -pos;     } } int query(int pos) {     int ret = 0;     while(pos) {         ret += tree[pos];         pos -= pos & -pos;     }     return ret; } node tmp[n]; void cdq(int l,int r) {     if(r <= l) return;     int mid = (l + r) >> 1;     cdq(l,mid);cdq(mid + 1,r);     int now = l,l = l,r = mid + 1;     while(l <= mid && r <= r) {         if(a[l].x <= a[r].x) {             if(a[l].opt == 1) {                 update(a[l].y,a[l].val);                 v.push_back(make_pair(a[l].y,a[l].val));             }             tmp[now++] = a[l++];         }         else {             if(a[r].opt == 2) ans[a[r].pos] += query(a[r].y);             else if(a[r].opt == 3) ans[a[r].pos] -= query(a[r].y);             tmp[now++] = a[r++];         }     }     while(l <= mid) tmp[now++] = a[l++];     while(r <= r) {         if(a[r].opt == 2) ans[a[r].pos] += query(a[r].y);         else if(a[r].opt == 3) ans[a[r].pos] -= query(a[r].y);         tmp[now++] = a[r++];     }     for(int i = l;i <= r;++i) a[i] = tmp[i];     int k = v.size();     for(int i = 0;i < k;++i) update(v[i].first,-v[i].second);     v.clear(); } int main() {     int n = read(),q = read(),now = 0;     for(int i = 1;i <= n;++i) {         tt[i] = read();         a[++tot].x = i + tt[i],a[tot].y = i - tt[i] + bl;         a[tot].opt = 1;a[tot].val = 1;         mx = max(mx,max(a[tot].x,a[tot].y));     }     for(int i = 1;i <= q;++i) {         scanf("%s",s + 1);         int x = read(),y = read();         if(s[1] == 'q') {             int x1 = x + tt[x] - y,x2 = x + tt[x] + y,y1 = x - tt[x] + bl - y,y2 = x - tt[x] + bl + y;              a[++tot].pos = ++now;a[tot].x = x2;a[tot].y = y2;a[tot].opt = 2;             a[++tot].pos = now;a[tot].x = x1 - 1;a[tot].y = y1 - 1;a[tot].opt = 2;             a[++tot].pos = now;a[tot].x = x1 - 1;a[tot].y = y2;a[tot].opt = 3;             a[++tot].pos = now;a[tot].x = x2;a[tot].y = y1 - 1;a[tot].opt = 3;         }         else {tt[x] = y;             a[++tot].opt = 1;             a[tot].x = x + tt[x];a[tot].y = x - tt[x] + bl;a[tot].val = 1;             mx = max(mx,max(a[tot].x,a[tot].y));         }     }    cdq(1,tot);     for(int i = 1;i <= now;++i) printf("%dn",ans[i]);     return 0; }