bzoj2120: 数颜色 带修莫队

时间：2021-06-09 23:52:02

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

题解:维护一个sum即答案,和一个记录每种颜色的笔的数目用的数组,然后O(1)转移,

/**************************************************************

    Problem: 2120

    User: walfy

    Language: C++

    Result: Accepted

    Time:564 ms

    Memory:48180 kb

****************************************************************/

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double eps=1e-6;

const int N=1000000+10,maxn=20000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

int a[N],belong[N];

struct query{

    int l,r,tim,id;

    bool operator <(const query&rhs)const{

        if(belong[l]==belong[rhs.l])

        {

            if(belong[r]==belong[rhs.r])return tim<rhs.tim;

            return r<rhs.r;

        }

        return l<rhs.l;

    }

}q[N];

struct change{

    int pos,suf,pre;

}ch[N];

int sum,co[N],ans[N],now[N];

void gao(int pos,int op)

{

    if(op==1)

    {

        if(co[a[pos]]==0)sum++;

        co[a[pos]]++;

    }

    else

    {

        if(co[a[pos]]==1)sum--;

        co[a[pos]]--;

    }

}

void go(int l,int r,int x,int d)

{

    if(l<=x&&x<=r)gao(x,-1),a[x]=d,gao(x,1);

    else a[x]=d;

}

int main()

{

    int n,m;

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

    int block=sqrt(n);

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

    {

        scanf("%d",&a[i]);

        now[i]=a[i];

        belong[i]=(i-1)/block+1;

    }

    int cnt1=0,cnt2=0;

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

    {

        char op[5];

        int x,y;scanf("%s%d%d",op,&x,&y);

        if(op[0]=='Q')q[++cnt1]={x,y,cnt2,cnt1};

        else ch[++cnt2]={x,y,now[x]},now[x]=y;

    }

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

    int l=1,r=0,ti=0;

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

    {

        while(ti<q[i].tim)ti++,go(l,r,ch[ti].pos,ch[ti].suf);

        while(ti>q[i].tim)go(l,r,ch[ti].pos,ch[ti].pre),ti--;

        while(l>q[i].l)l--,gao(l,1);

        while(r<q[i].r)r++,gao(r,1);

        while(l<q[i].l)gao(l,-1),l++;

        while(r>q[i].r)gao(r,-1),r--;

//        printf("%d -----%d %d %lld\n",l,r,ti,sum);

//        for(int j=0;j<=n;j++)printf("%d ",co[j]);puts("");

        ans[q[i].id]=sum;

    }

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

    return 0;

}

/********************

********************/

相关文章