【BZOJ】2120: 数颜色 带修改的莫队算法

时间：2023-03-10 05:32:41
【BZOJ】2120: 数颜色 带修改的莫队算法

【题意】给定n个数字，m次操作，每次询问区间不同数字的个数，或修改某个位置的数字。n,m<=10^4，ai<=10^6。

【算法】带修改的莫队算法

【题解】对于询问(x,y,t)，其中t是前面的修改次数，所有修改记录改前和改后。

首先按belong[x]，然后按belong[y]，最后按t排序。（块大小n^(2/3)）

移动询问，先移动t，然后移动x和y，运用对称差操作实现。如果移动t前修改格访问过，先删除影响，修改，再加回。

区间莫队需要注意的还有操作顺序问题，区间先拓展再收缩，以及修改的开闭边界问题需要特别注意（左右是不同的）。

哦还有还有，初始是(0,0,0)的话，令vis[0]=1。

为什么我说得这么草率？因为写完了糖果公园后就真的没什么好说的了……当然还是在区间移动上面栽了一下233。

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int belong[maxn],n,m,pre[maxn],c[maxn],d[],ans=,c0,c1,ANS[maxn];

bool vis[maxn];

struct q{int x,y,t,id;}b[maxn];

struct mo{int x,y,pre;}a[maxn];

bool cmp(q a,q b){return belong[a.x]<belong[b.x]||(belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y])||

(belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]&&a.t<b.t);}

void solve(int x){

    if(!vis[x])ans+=(++d[c[x]]==);

    else ans-=(--d[c[x]]==);//

    vis[x]^=;

}

void modify(int x,int y){

    if(!vis[x])c[x]=y;

    else solve(x),c[x]=y,solve(x);

}

char s[];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&c[i]),pre[i]=c[i];

    for(int i=;i<=m;i++){

        int u,v;

        scanf("%s%d%d",s,&u,&v);

        if(s[]=='R')a[++c0]=(mo){u,v,pre[u]},pre[u]=v;

        else {if(u>v)swap(u,v);b[++c1]=(q){u,v,c0,c1};}

    }

    int Q=(int)pow(n,2.0/);

    for(int i=;i<=n;i++)belong[i]=(i-)/Q+;

    sort(b+,b+c1+,cmp);

    vis[]=;//

    for(int i=;i<=c1;i++){

        for(int j=b[i-].t+;j<=b[i].t;j++)modify(a[j].x,a[j].y);

        for(int j=b[i-].t;j>b[i].t;j--)modify(a[j].x,a[j].pre);

        for(int j=b[i-].y+;j<=b[i].y;j++)solve(j);//

        for(int j=b[i-].x-;j>=b[i].x;j--)solve(j);

        for(int j=b[i-].x;j<b[i].x;j++)solve(j);

        for(int j=b[i-].y;j>b[i].y;j--)solve(j);

        ANS[b[i].id]=ans;

    }

    for(int i=;i<=c1;i++)printf("%d\n",ANS[i]);

    return ;

}

相关文章