bzoj4170 极光
程序员文章站
2022-04-28 12:19:09
题意
把每个位置的点都看成是一个二维坐标系中的点。比如第$i$个点就是$(i,a[i])$。
有两种操作 ......
题面
题意
把每个位置的点都看成是一个二维坐标系中的点。比如第\(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("%d\n",ans[i]); return 0; }
上一篇: BZOJ2564: 集合的面积(闵可夫斯基和 凸包)
下一篇: 刚刚一辆劳斯莱斯从我身边开过