BZOJ2120：数颜色（莫队版）

浅谈莫队：https://www.cnblogs.com/AKMer/p/10374756.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2120

分块做法：https://www.cnblogs.com/AKMer/p/10373457.html

树套树做法：https://www.cnblogs.com/AKMer/p/10189008.html

裸的带修改莫队，用一个桶维护区间内元素，每次桶从\(0\)变\(1\)或者从\(1\)变\(0\)就把全局\(ans\)加一或减一即可。

时间复杂度：\(O(n^{\frac{5}{3}})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e4+5,maxv=1e6+5;

char s[5];

int n,m,block,ans,cnt1,cnt2,nowl,nowr,t;

int a[maxn],bel[maxn],cnt[maxv],lst[maxn];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct query {

    int l,r,tim,id,res;

    query() {}

    query(int _l,int _r,int _tim,int _id) {

        l=_l,r=_r,tim=_tim,id=_id;

    }

    bool operator<(const query &a)const {

        if(bel[l]==bel[a.l]&&bel[r]==bel[a.r])return tim<a.tim;

        if(bel[l]==bel[a.l])return bel[l]&1?bel[r]<bel[a.r]:bel[r]>bel[a.r];

        return bel[l]<bel[a.l];

    }

}q[maxn];

struct modify {

    int pos,col,lst;

    modify() {}

    modify(int _pos,int _col,int _lst) {

        pos=_pos,col=_col,lst=_lst;

    }

}c[maxn];

bool cmp(query a,query b) {

    return a.id<b.id;

}

void change(int pos,int col) {

    if(pos>=nowl&&pos<=nowr) {

        if(!cnt[col])ans++;

        if(cnt[a[pos]]==1)ans--;

        cnt[a[pos]]--,cnt[col]++;

    }a[pos]=col;

}

void update(int col,int v) {

    if(cnt[col]==1&&v==-1)ans--;

    if(cnt[col]==0&&v==1)ans++;

    cnt[col]+=v;

}

int main() {

    n=read(),m=read(),block=pow(n,2.0/3);

    for(int i=1;i<=n;i++)

        lst[i]=a[i]=read(),bel[i]=(i-1)/block+1;

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

        scanf("%s",s+1);

        if(s[1]=='Q') {

            int l=read(),r=read();

            q[++cnt1]=query(l,r,cnt2,i);

        }

        else {

            int pos=read(),col=read();

            c[++cnt2]=modify(pos,col,lst[pos]);

            lst[pos]=col;

        }

    }

    sort(q+1,q+cnt1+1);

    nowl=1,nowr=0,t=0;

    for(int i=1;i<=cnt1;i++) {

        while(t<q[i].tim)t++,change(c[t].pos,c[t].col);

        while(t>q[i].tim)change(c[t].pos,c[t].lst),t--;

        while(nowl<q[i].l)update(a[nowl++],-1);

        while(nowl>q[i].l)update(a[--nowl],1);

        while(nowr<q[i].r)update(a[++nowr],1);

        while(nowr>q[i].r)update(a[nowr--],-1);

        q[i].res=ans;

    }

    sort(q+1,q+cnt1+1,cmp);

    for(int i=1;i<=cnt1;i++)

        printf("%d\n",q[i].res);

    return 0;

}

巴特西

BZOJ2120：数颜色（莫队版）

最新文章

热门文章