[BZOJ2120/Luogu1903]数颜色(莫队算法)

发布于 2018-02-05  91 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2120/Luogu1903]数颜色(莫队算法)

Description

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

Http

BZOJ
Luogu

Tag

莫队算法,离线

解决思路

莫队算法把询问离线下来,排序后移动左右指针得到答案。
但这里有修改操作,怎么办呢?
可以在把询问左右区间离线下来的同时记录时间,记录是第一个修改操作后的,那么回答询问的时候再移动时间指针,把要修改的修改掉,不要修改的改回去。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=5001000;
const int inf=2147483647;

class Question//询问
{
public:
    int l,r,tim,id;
};

class Modify//修改
{
public:
    int pos,before,col;
};

int n,m,nowans=0;
int L,R,Tim;
int Col[maxN],InitCol[maxN],Sum[maxN],Belong[maxN];
Question Q[maxN];
Modify M[maxN];
int Ans[maxN];

bool cmp(Question A,Question B);
void TimeMove(int pos,int col);
void PosMove(int col,int opt);

int main()
{
    scanf("%d%d",&n,&m);
    int size=pow(n,0.66666666);
    for (int i=1;i<=n;i++) Belong[i]=(i-1)/size+1;
    for (int i=1;i<=n;i++) scanf("%d",&Col[i]),InitCol[i]=Col[i];
    int mcnt=0,qcnt=0;
    for (int i=1;i<=m;i++)
    {
        char opt;cin>>opt;
        if (opt=='Q')
        {
            int l,r;scanf("%d%d",&l,&r);
            Q[++qcnt]=(Question){l,r,mcnt,qcnt};
        }
        else
        {
            int pos,col;scanf("%d%d",&pos,&col);
            M[++mcnt]=(Modify){pos,Col[pos],col};
            Col[pos]=col;
        }
    }
    for (int i=1;i<=n;i++) Col[i]=InitCol[i];
    L=1,R=0;Tim=0;
    sort(&Q[1],&Q[qcnt+1],cmp);
    for (int i=1;i<=qcnt;i++)
    {
        while (Tim<Q[i].tim) TimeMove(M[Tim+1].pos,M[Tim+1].col),Tim++;
        while (Tim>Q[i].tim) TimeMove(M[Tim].pos,M[Tim].before),Tim--;
        while (L<Q[i].l) PosMove(Col[L],-1),L++;
        while (L>Q[i].l) PosMove(Col[L-1],1),L--;
        while (R>Q[i].r) PosMove(Col[R],-1),R--;
        while (R<Q[i].r) PosMove(Col[R+1],1),R++;
        Ans[Q[i].id]=nowans;
    }
    for (int i=1;i<=qcnt;i++) printf("%d\n",Ans[i]);
    return 0;
}

bool cmp(Question A,Question B)
{
    return (Belong[A.l]!=Belong[B.l])?(A.l<B.l):((Belong[A.r]!=Belong[B.r])?(A.r<B.r):(A.tim<B.tim));
}

void TimeMove(int pos,int col)//移动时间
{
    if ((pos>=L)&&(pos<=R)) PosMove(Col[pos],-1),PosMove(col,1);
    Col[pos]=col;
    return;
}

void PosMove(int col,int opt)//移动位置
{
    nowans-=(Sum[col]>0);
    Sum[col]+=opt;
    nowans+=(Sum[col]>0);
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2120/Luogu1903]数颜色(莫队算法)


HNCJ OIer 一枚