题解：P10633 BZOJ2989 数列/BZOJ4170 极光

· · 题解

我们将数列中的每个数转化成点 (i,a_i) 表示在平面上，询问即为求与 (x,a_x) 曼哈顿距离不超过 k 的点有多少个。把这个范围表示出来，可以发现在平面上呈一个菱形如图中 ABCD。

这种范围不是特别好表示，我们考虑将每个点绕坐标系原点顺时针转动 45 度，得到 \left(\dfrac{i+a_i}{\sqrt2},\dfrac{-i+a_i}{\sqrt2}\right)，于是我们将菱形的限制转换成了正方形的限制，而这是比较方便维护的。当然把 \sqrt2 拿掉变成相似变换是完全无影响的。

对于一个询问，我们现在需要求一个类似于二维数点的东西，但是由于修改操作，我们增添一维时间轴，此时我们有三个限制要满足（时间，横纵坐标），类似于三维偏序的可以进行 CDQ 分治解决，时间复杂度为 \mathcal{O}(n\log^2 n)。

%:include <bits/stdc++.h>
using namespace std;
// 快读

const int N=6e4+5;
const int L=3.5e5+5;
int n,q,cur,m,a[N],ans[N],lm,cez[L];
struct Node {int id,x,y,op;} v[L],tmp[L];

int t[L];
#define lowbit(x) (x&-x)
void change(int p,int x) {for(;p<=lm;p+=lowbit(p)) t[p]+=x;}
int ask(int p) {int x=0; for(;p;p-=lowbit(p)) x+=t[p]; return x;}
void CDQ(int l,int r) {
    if(l==r) return ;
    int mid=l+r>>1,loc=l,p=l,q=mid+1;
    CDQ(l,mid),CDQ(mid+1,r);
    while(q<=r) {
        while(p<=mid&&v[p].x<=v[q].x) {
            if(!v[p].op) change(v[p].y,1);
            tmp[loc++]=v[p++];
        }
        if(v[q].op) ans[v[q].id]+=ask(v[q].y)*v[q].op;
        tmp[loc++]=v[q++];
    }
    for(int i=l;i<p;i++) if(!v[i].op) change(v[i].y,-1);
    for(int i=p;i<=mid;i++) tmp[loc++]=v[i];
    for(int i=l;i<=r;i++) v[i]=tmp[i];
}

int main() {
    n=rd(),q=rd();
    for(int i=1;i<=n;i++) {
        a[i]=rd(),cez[++m]=a[i]-i;
        v[m]=(Node){0,a[i]+i,a[i]-i,0};
    }
    for(int i=1;i<=q;i++) {
        char ch=getchar();
        while(!isalpha(ch)) ch=getchar();
        if(ch=='M') {
            int x=rd(),k=rd(); a[x]=k;
            cez[++m]=k-x,v[m]=(Node){0,k+x,k-x,0};
        } else {
            ++cur; int x=rd(),k=rd();
            cez[++m]=a[x]-x+k,v[m]=(Node){cur,a[x]+x+k,a[x]-x+k,1};
            cez[++m]=a[x]-x+k,v[m]=(Node){cur,a[x]+x-k-1,a[x]-x+k,-1};
            cez[++m]=a[x]-x-k-1,v[m]=(Node){cur,a[x]+x+k,a[x]-x-k-1,-1};
            cez[++m]=a[x]-x-k-1,v[m]=(Node){cur,a[x]+x-k-1,a[x]-x-k-1,1};
        }
    }
    sort(cez+1,cez+1+m),lm=unique(cez+1,cez+1+m)-cez-1;
    for(int i=1;i<=m;i++) v[i].y=lower_bound(cez+1,cez+1+lm,v[i].y)-cez;
    CDQ(1,m); for(int i=1;i<=cur;i++) printf("%d\n",ans[i]);
    return 0;
}