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

题目描述

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：

1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。

2、 R P Col 把第P支画笔替换为颜色Col。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入输出格式

输入格式：

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。

第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式：

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

输入输出样例

输入样例#1：

6 5

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Q 1 4

Q 2 6

输出样例#1：

说明

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

来源：bzoj2120

本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。

莫队入门中。。(省略号是动态的)

屠龙宝刀点击就送

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#define N 1000500

using namespace std;

struct node

{

    int l,r,id,bel,tim,ans;

}s[N];

bool cmp(node a,node b)

{

    if(a.bel==b.bel) return a.r<b.r;

    else return a.bel<b.bel;

}

bool comp(node a,node b)

{

    return a.id<b.id;

}

struct nodee

{

    int bef,aft,pos;

}ss[N];

int C,n,m,col[N],tot,now,ans,sum[N];

void update(int x,int y)

{

    sum[x]+=y;

    if(y==&&sum[x]==) ans++;

    else if(y==-&&!sum[x]) ans--;

}

int Main()

{

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

    C=(int)sqrt((double)n);

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

    char opt[];

    for(int x,y;m--;)

    {

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

        if(opt[]=='Q')

        {

            s[++tot].l=x;

            s[tot].r=y;

            s[tot].bel=(x-)/C+;

            s[tot].tim=now;

            s[tot].id=tot;

        }

        else if(opt[]=='R')

        {

            ss[++now].pos=x;

            ss[now].aft=y;

        }

    }

    now=;

    sort(s+,s++tot,cmp);

    for(int L=,R=,i=;i<=tot;++i)

    {

        while(now<s[i].tim)

        {

            now++;

            ss[now].bef=col[ss[now].pos];

            if(ss[now].pos<=R&&ss[now].pos>=L)

            {

                update(ss[now].bef,-);

                update(ss[now].aft,);

            }

            col[ss[now].pos]=ss[now].aft;

        }

        while(now>s[i].tim)

        {

            if(ss[now].pos<=R&&ss[now].pos>=L)

            {

                update(ss[now].aft,-);

                update(ss[now].bef,);

            }

            col[ss[now].pos]=ss[now].bef;

            now--;

        }

        while(L<s[i].l) update(col[L++],-);

        while(L>s[i].l) update(col[--L],);

        while(R<s[i].r) update(col[++R],);

        while(R>s[i].r) update(col[R--],-);

        s[i].ans=ans;

    }

    sort(s+,s++tot,comp);

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

    return ;

}

int sb=Main();

int main(int argc,char *argv[]){;}

巴特西

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

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章