BZOJ 2453 维护队列

题目大意

给你一堆数，求$[L,R]$内不同元素的个数。

这道题我直接写的分块+莫队，在莫队排序的基础上加了一层时间作为第一关键字，之后直接暴力莫队就可以了。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,c[1000010],prx[1000010],pry[1000010],cnt[1000010],ans[1000010],tot,tmp,keeper;
char mode[10];
struct query
{
    int x,y,id,blk,pr;
}q[10010];
bool cmp(query tx,query ty)
{
    if(tx.pr==ty.pr&&tx.blk==ty.blk) return tx.y<ty.y;
    if(tx.pr==ty.pr) return tx.blk<ty.blk;
    return tx.pr<ty.pr; 
}
void update(int tx,int ty,int l,int r)
{
    for(int i=tx+1;i<=ty;++i)
    {
        if(prx[i]>=l&&prx[i]<=r)
        {
            cnt[c[prx[i]]]--;
            if(!cnt[c[prx[i]]]) tmp--;
            if(!cnt[pry[i]]) ++tmp;
            cnt[pry[i]]++;
        }
        c[prx[i]]=pry[i];
    }
    return;
}
void init()
{
    if(q[0].pr!=q[1].pr) update(q[0].pr,q[1].pr,q[0].x,q[0].y);
    for(int i=q[1].x;i<=q[1].y;++i)
    {
        if(!cnt[c[i]]) tmp++;
        cnt[c[i]]++;
    }
    ans[q[1].id]=tmp;
    return;
}
void movel(int tx,int ty)
{
    if(tx<ty) for(int i=tx;i<ty;++i)
    {
        cnt[c[i]]--;
        if(!cnt[c[i]]) tmp--;
    }
    else for(int i=tx-1;i>=ty;--i)
    {
        if(!cnt[c[i]]) tmp++;
        cnt[c[i]]++;
    }
}
void mover(int tx,int ty)
{
    if(tx<ty) for(int i=tx+1;i<=ty;++i)
    {
        if(!cnt[c[i]]) tmp++;
        cnt[c[i]]++;
    }
    else for(int i=tx;i>ty;--i)
    {
        cnt[c[i]]--;
        if(!cnt[c[i]]) tmp--;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",c+i);
    keeper=sqrt(n);
    q[0].pr=tmp=1;
    for(int i=1;i<=m;++i)
    {
        scanf("%s",mode);
        switch(mode[0])
        {
            case 'Q':
            {
                ++tot;
                scanf("%d%d",&q[tot].x,&q[tot].y);
                q[tot].id=tot,q[tot].blk=q[tot].x/keeper+1,q[tot].pr=tmp;
                break;
            }
            case 'R':
            {
                tmp++;
                scanf("%d%d",prx+tmp,pry+tmp);
                break;
            }
        }
    }
    tmp=0;
    sort(q+1,q+tot+1,cmp);
    init();
    for(int i=2;i<=m;++i)
    {
        if(q[i-1].pr!=q[i].pr) update(q[i-1].pr,q[i].pr,q[i-1].x,q[i-1].y);
        movel(q[i-1].x,q[i].x);
        mover(q[i-1].y,q[i].y);
        ans[q[i].id]=tmp;
    }
    for(int i=1;i<=tot;++i) printf("%d\n",ans[i]);
    return 0;
}