解题：luogu p1903 数颜色 / 维护队列

· · 题解

题面

前排提醒：这篇题解不太是(啥玩意=。=？？？)正解，只能在O2优化后通过(O2后最快的话最慢的一个点跑了300+ms，不O2直接TLE(或许有什么手写bitset这种东西可以过=。=？))

初学分块的蒟蒻用暴力的分块卡过去了想写篇题解，dalao们轻喷=。=

直接分块+bitset，离散化后记录每块内每种颜色出现的次数，这样一次修改是O(1)的(不算离散化的话)。然而查询时因为要合并块，所以复杂度是整块长度之和这个级别的的(虽然有个bitset的\frac{1}{32})，直接把块大小siz设成sqrt(n)做大概会比较慢。

为了提高效率，这里可以适当加大块的大小，这样块合并会变少而零散区间的统计会变多，在这个题效率会更高一点(我一开始弄了一个n^{\frac{3}{5}}的块大小(块最大的时候大概是660)卡过去了，最慢的点跑了600+ms，后来又试了试然后还加了个“输出优化(不知道有没有用啊=。=)”，把块大小搞成n^{\frac{3}{4}}跑的更快了些(块最大的时候大概是3400)，就是上面说的300ms+)

// luogu-judger-enable-o2
#include<cmath>
#include<cstdio>
#include<cctype>
#include<bitset>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=50005,M=100005,Sq=20;
struct a
{
    int typ;
    int ll,rr;
}q[N];
int n,m,t1,t2,t3,t4,sqr,cnt,xnt,len;
int pts[Sq][2],app[Sq][M]; 
int a[N],blo[N],uni[2*N];
bitset<M> sta[Sq],qry; 
char rd[5];
inline int read()
{
    int ret=0;
    char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        ret=(ret<<1)+(ret<<3)+(ch^48),ch=getchar();
    return ret;
}
inline void write(int x)
{
    if(x>9) write(x/10);
    putchar(x%10+48);
}
int main()
{
    register int i,j;
    n=read(),m=read(),xnt=n;
    sqr=pow(n,0.75),pts[cnt=1][0]=1;
    for(i=1;i<=n;i++)
    {
        a[i]=read(),uni[i]=a[i];
        blo[i]=(i-1)/sqr+1;
        if(i%sqr==0)
        {
            pts[cnt++][1]=i;
            pts[cnt][0]=i+1; 
        }
    }
    pts[cnt][1]=n; 
    for(i=1;i<=m;i++)
    {
        scanf("%s",rd),t1=read(),t2=read();
        q[i].ll=t1,q[i].rr=t2,q[i].typ=(rd[0]=='R');
        if(q[i].typ) uni[++xnt]=t2;
    }
    sort(uni+1,uni+1+xnt),len=unique(uni+1,uni+1+xnt)-uni-1;
    for(i=1;i<=n;i++)
    {
        a[i]=lower_bound(uni+1,uni+1+len,a[i])-uni;
        if(++app[blo[i]][a[i]]==1) sta[blo[i]][a[i]]=true;
    }
    for(i=1;i<=m;i++)
    {
        t1=q[i].ll,t2=q[i].rr;
        if(q[i].typ)
        {
            int bel=blo[t1],newc=lower_bound(uni+1,uni+1+len,t2)-uni;
            if(!(--app[bel][a[t1]])) sta[bel][a[t1]]=false;
            if(++app[bel][newc]==1) sta[bel][newc]=true; a[t1]=newc;
        }
        else 
        {
            qry.reset(),t3=blo[t1],t4=blo[t2];
            if(t3!=t4)
            {
                for(j=t1;j<=pts[t3][1];j++) qry[a[j]]=true;
                for(j=pts[t4][0];j<=t2;j++) qry[a[j]]=true;
                for(j=t3+1;j<=t4-1;j++) qry|=sta[j];
            }
            else for(j=t1;j<=t2;j++) qry[a[j]]=true;
            write((int)qry.count()),puts("");
        }
    }
    return 0;
}