AC日记——【模板】分块/带修改莫队（数颜色） 洛谷 P1903

【模板】分块/带修改莫队（数颜色）

思路：

　　带修改莫队；

　　(伏地膜xxy)；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 1000005

#define maxnum 1000005

int bel[maxn],blo;

struct QueryType {

    int l,r,k,id;

    bool operator<(const QueryType pos)const

    {

        if(bel[l]==bel[pos.l])

        {

            if(bel[r]==bel[pos.r]) return k<pos.k;

            else return bel[r]<bel[pos.r];

        }

        else return bel[l]<bel[pos.l];

    }

};

struct QueryType qu[maxn];

int n,m,ai[maxn],now,num[maxnum],ans[maxn];

int ch[maxn],to[maxn],back[maxn],cntq,cntc;

int l=,r,k;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void updatak(int x,bool di)

{

    if(di)

    {

        back[x]=ai[to[x]];

        ai[to[x]]=ch[x];

        if(to[x]<=r&&to[x]>=l)

        {

            num[back[x]]--;

            if(!num[back[x]]) now--;

            num[ch[x]]++;

            if(num[ch[x]]==) now++;

        }

    }

    else

    {

        ai[to[x]]=back[x];

        if(to[x]<=r&&to[x]>=l)

        {

            num[ch[x]]--;

            if(!num[ch[x]]) now--;

            num[back[x]]++;

            if(num[back[x]]==) now++;

        }

    }

}

inline void updata(int x,bool di)

{

    x=ai[x];

    if(di)

    {

        if(!num[x])now++;

        num[x]++;

    }

    else

    {

        if(num[x]==)now--;

        num[x]--;

    }

}

int main()

{

    in(n),in(m),blo=sqrt(n);

    for(int i=;i<=n;i++) in(ai[i]),bel[i]=(i-)/blo;

    char op[];

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

    {

        scanf("%s",op);

        if(op[]=='Q')

        {

            in(qu[++cntq].l);

            in(qu[cntq].r);

            if(qu[cntq].l>qu[cntq].r)

            {

                swap(qu[cntq].l,qu[cntq].r);

            }

            qu[cntq].id=cntq;

            qu[cntq].k=cntc;

        }

        else in(to[++cntc]),in(ch[cntc]);

    }

    sort(qu+,qu+cntq+);

    for(int i=;i<=cntq;i++)

    {

        while(k<qu[i].k) updatak(++k,true);

        while(k>qu[i].k) updatak(k--,false);

        while(r<qu[i].r) updata(++r,true);

        while(r>qu[i].r) updata(r--,false);

        while(l<qu[i].l) updata(l++,false);

        while(l>qu[i].l) updata(--l,true);

        ans[qu[i].id]=now;

    }

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

    return ;

}