题解：P10633 BZOJ2989 数列/BZOJ4170 极光

· · 题解

这道题实际上就是维护一个平面直角坐标系，每次加一个点，求与一个点曼哈顿距离 \le k 的点数。

trick：(x,y) 转化为 (x+y,-x+y)，转化为一个点为中心，边长为 2k 的正方形包含的点数。

二维线段树即可，即外层区间线段树，内层动态开点权值线段树。

int n,m,a[N],rt[V<<2];
#define mid (l+r>>1)
struct SGT1 {
    int num,ls[V<<7],rs[V<<7],val[V<<7],cnt;
    void upd(int &id,int l,int r,int x) {if(!id) id=++num; val[id]++; if(l==r) return; x<=mid?upd(ls[id],l,mid,x):upd(rs[id],mid+1,r,x);}
    int qry(int id,int l,int r,int L,int R) {return !id?0:L<=l&&r<=R?val[id]:(L<=mid?qry(ls[id],l,mid,L,R):0)+(R>mid?qry(rs[id],mid+1,r,L,R):0);}
}S;
struct SGT2 {
    #define ls (id<<1)
    #define rs (id<<1|1)
    void upd(int id,int l,int r,int x,int y) {S.upd(rt[id],-V,V,y); if(l==r) return; x<=mid?upd(ls,l,mid,x,y):upd(rs,mid+1,r,x,y);}
    int qry(int id,int l,int r,int L,int R,int _L,int _R) {return L<=l&&r<=R?S.qry(rt[id],-V,V,_L,_R):(L<=mid?qry(ls,l,mid,L,R,_L,_R):0)+(R>mid?qry(rs,mid+1,r,L,R,_L,_R):0);}
}T;
void QwQ() {
    n=rd(),m=rd(); for(int i=1;i<=n;i++) a[i]=rd(),T.upd(1,1,V,a[i]+i,a[i]-i);
    for(int x,y;m--;) {
        string s; cin>>s,x=rd(),y=rd();
        if(s=="Modify") a[x]=y,T.upd(1,1,V,y+x,y-x);
        else wr(T.qry(1,1,V,a[x]+x-y,a[x]+x+y,a[x]-x-y,a[x]-x+y),"\n"); 
    }
}