基本思路

将坐标$(a_i,i)$看作一个点,那么本题转化为每次资磁插入一个点,查询已插入的点中,离某个点的曼哈顿距离小于等于$k$的点数。
曼哈顿距离转切比雪夫距离的套路,将坐标变成$(a_i+i,a_i-i)$后,两点的距离变成$max(|x_1-x_2|,|y_1-y_2|)$,那么查询一个矩形区域内的点数即可。如果是先一堆插入再一堆查询,那么按照x坐标建立主席树,每棵树内维护y坐标在某个区间的点有多少个即可。
问题是插入和查询是交错的,这怎么办呢?

What is 二进制分组 you may ask

对于每$2^t$个插入的点归到一组,对每组建立“一组”主席树,然后查询时在所有主席树组里面查询即可。
具体方法是,假如插入了一个点,建立一个大小为1的组。
假如它与上一个组大小相同,将它与上一个组的主席树都暴力ban掉,然后重建一棵新的主席树。
譬如现在一些组大小是16,4,2,1,我添加一个大小为1的组,然后不断合并:
16,4,2,1,1
16,4,2,2
16,4,4
16,8
发现每次的组数是log级别的,所以每一个点被合并的次数也是log级别的,所以复杂度就是$O(nlog^2n)$的。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=160005,LIM=160000,M=1800005,Y=60000,inf=0x3f3f3f3f;
typedef pair<int,int> PR;
int n,Q,top,SZ,js;
struct node{int ls,rs,sz;}tr[M];
int a[N],rub[M],rt[20][N],vis[M];
vector<PR> OvO[20],kl;

int newnode() {
    int re;
    if(top) re=rub[top--];
    else re=++SZ;
    vis[re]=1;return re;
}
void ins(int &x,int y,int l,int r,int wz) {
    x=newnode(),tr[x]=tr[y],++tr[x].sz;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(wz<=mid) ins(tr[x].ls,tr[y].ls,l,mid,wz);
    else ins(tr[x].rs,tr[y].rs,mid+1,r,wz);
}
void del(int x) {
    if(!vis[x]) return;
    if(tr[x].ls) del(tr[x].ls);
    if(tr[x].rs) del(tr[x].rs);
    tr[x].ls=tr[x].rs=tr[x].sz=vis[x]=0,rub[++top]=x;
}
int query(int x,int y,int s,int t,int l,int r) {
    if(l<=s&&t<=r) return tr[y].sz-tr[x].sz;
    int mid=(s+t)>>1,re=0;
    if(l<=mid) re=query(tr[x].ls,tr[y].ls,s,mid,l,r);
    if(mid+1<=r) re+=query(tr[x].rs,tr[y].rs,mid+1,t,l,r);
    return re;
}

void work(int x,int y) {
    OvO[++js].push_back((PR){x,y});
    ins(rt[js][1],rt[js][0],1,LIM,y);
    while(js>1&&OvO[js].size()==OvO[js-1].size()) {
        kl.clear();int k1=0,k2=0,sz1=OvO[js].size(),sz2=OvO[js-1].size();
        for(RI i=1;i<=sz1;++i) del(rt[js][i]);
        for(RI i=1;i<=sz2;++i) del(rt[js-1][i]);
        for(RI i=1;i<=sz1+sz2;++i) {
            if(k2>=sz2||(k1<sz1&&OvO[js][k1]<OvO[js-1][k2]))
                kl.push_back(OvO[js][k1++]);
            else kl.push_back(OvO[js-1][k2++]);
            ins(rt[js-1][i],rt[js-1][i-1],1,LIM,kl[i-1].second);
        }
        OvO[js-1]=kl,OvO[js].clear(),--js;
    }
}
int getans(int x,int y,int k) {
    int re=0;
    for(RI i=1;i<=js;++i) {
        int k1=lower_bound(OvO[i].begin(),OvO[i].end(),(PR){x-k,0})-OvO[i].begin();
        int k2=lower_bound(OvO[i].begin(),OvO[i].end(),(PR){x+k,inf})-OvO[i].begin();
        re+=query(rt[i][k1],rt[i][k2],1,LIM,max(1,y-k),min(y+k,LIM));
    }
    return re;
}
int main()
{
    char ch[10];int x,y;
    n=read(),Q=read();
    for(RI i=1;i<=n;++i) a[i]=read(),work(a[i]+i,a[i]-i+Y);
    while(Q--) {
        scanf("%s",ch),x=read(),y=read();
        if(ch[0]=='M') a[x]=y,work(a[x]+x,a[x]-x+Y);
        else printf("%d\n",getans(a[x]+x,a[x]-x+Y,y));
    }
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *