洛谷 P1903 数颜色 题解【莫队】【分块】

点击量：93

    莫队进阶？之带修莫队。

目录

题目描述

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

1.  Q L R代表询问你从第\(L\)支画笔到第\(R\)支画笔中共有几种不同颜色的画笔。
2.  R P Col 把第\(P\)支画笔替换为颜色\(Col\)。

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

 

输入输出格式

输入格式：

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

 

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

 

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

 

输出格式：

对于每一个\(\text{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：

4
4
3
4

题解：

    这道题有莫队的影子，但是会进行单点修改。不过单点修改对于莫队来说也是可以完成的，我们只要像移动\(l,r\)指针一样移动修改的操作时间\(t\)就可以了。（这道题原题是\(10^4\)的范围，但是luogu的评测姬太快导致暴力可过变成了\(5\times 10^4\)）

    在普通莫队中，我们把\(l\)限制在\(L=\sqrt{n}\)的区域里（本文令\(n,m\)同阶）然后维持\(r\)的单调性，保证了每个块中\(l,r\)移动的距离分别不超过\(n\)，共\(\sqrt{n}\)次。此时我们考虑维护时间戳\(t\)的单调性（可能考虑到修改操作的常数较大？），此时在这些操作中，\(l\)的总移动距离有\(nL\)（每次操作最多移动\(O(L)\)的距离），\(r\)的移动距离是\((\frac nL)^2\times L\)（是每段\(r\)中期望有\(\frac nL\)个询问，每个询问会跑\(O(L)\)的长度，再乘上\(l\)的段数\(\frac nL\)。）而\(t\)的移动距离是总段数\((\frac nL)^2\)乘上长度\(n\)。那么没有确定块长\(L\)的时间复杂度是：

$$O(nL+(\frac nL)^2\times (L+n))$$

    我们接下来要确定分块大小，但是上述式子取最小值的情况始终没证出来，网上都说是取\(L=n^{\frac 23}\)，这篇博客可能有点道理，剩下的式子推的实在是麻烦，总之带到时间复杂度中去，分块成\(L=n^{\frac 23}\)后，得到复杂度是\(O(n^{\frac 53}+n^{\frac 53}+n^{\frac 43})=O(n^{\frac 53})\)，可以勉强在\(2s\)内过掉这个\(5\times 10^4\)。

    因此莫队最重要的是排序方式，剩下的都比较单一，因此看到莫队题时，首先要解决好怎么排序这一问题。

Code：

（这份代码中时间戳还可以继续优化）

#include<cstdio>
#include<algorithm>
#include<cmath>
int b[50010];
struct query
{
    int l,r,t,ans,i;
    friend bool operator <(query x,query y)
    {
        if(b[x.l]!=b[y.l])
            return x.l<y.l;
        if(b[x.r]!=b[y.r])
            return x.r<y.r;
        return x.t<y.t;
    }
    query(int l,int r,int t,int i)
    {
        this->l=l;
        this->r=r;
        this->t=t;
        this->i=i;
    }
    query(){}
}q[50010];
bool cmp(query x,query y)
{
    return x.i<y.i;
}
struct change
{
    int p,x,y;//原来是x 改成y了
    change(int p,int x,int y)
    {
        this->p=p;
        this->x=x;
        this->y=y;
    }
    change(){}
}c[50010];
int a[50010];
int qcnt=0,ccnt=0;
int app[1000010],sum=0;
void modify(int p,int x)//把哪个颜色加还是减
{
    int flag=(app[p]>0);
    app[p]+=x;
    if(!app[p]&&flag)
        --sum;
    if(!flag&&app[p]>0)
        ++sum;
}
int main()
{
    int n,m,u,v;
    char op[10];
    scanf("%d%d",&n,&m);
    int par=pow(n,0.66);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        b[i]=ceil((double)i/par);
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%s",op);
        scanf("%d%d",&u,&v);
        if(op[0]=='Q')
            q[++qcnt]=query(u,v,ccnt,i);
        else
        {
            c[++ccnt]=change(u,a[u],v);
            a[u]=v;
        }
    }
    for(int i=ccnt;i;--i)
        a[c[i].p]=c[i].x;
    std::sort(q+1,q+1+qcnt);
    int l=1,r=0,t=0;
    for(int i=1;i<=qcnt;++i)
    {
        while(t<q[i].t)//假定t停在一个已修改的地方
        {
            ++t;
            if(l<=c[t].p&&c[t].p<=r)//x是原颜色
            {
                modify(c[t].x,-1);
                modify(c[t].y,1);
            }
            a[c[t].p]=c[t].y;
        }
        while(t>q[i].t)
        {
            if(l<=c[t].p&&c[t].p<=r)
            {
                modify(c[t].y,-1);
                modify(c[t].x,1);
            }
            a[c[t].p]=c[t].x;
            --t;
        }
        while(l<q[i].l)
            modify(a[l++],-1);
        while(l>q[i].l)
            modify(a[--l],1);
        while(r<q[i].r)
            modify(a[++r],1);
        while(r>q[i].r)
            modify(a[r--],-1);
        q[i].ans=sum;
    }
    std::sort(q+1,q+1+qcnt,cmp);
    for(int i=1;i<=qcnt;++i)
        printf("%d\n",q[i].ans);
    return 0;
}