欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj4170 极光

程序员文章站 2022-04-28 12:19:09
题意 把每个位置的点都看成是一个二维坐标系中的点。比如第$i$个点就是$(i,a[i])$。 有两种操作 ......

题目链接

题面

bzoj4170 极光

题意

把每个位置的点都看成是一个二维坐标系中的点。比如第\(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;
}