题解 P1903 【[国家集训队]数颜色】

jzqjzq · 2018-01-25 15:29:06 · 题解

这估计是一个比暴力复杂度还劣的做法……

直接大力分块，对每个块维护bitset

修改直接做，查询直接合并bitset

时间复杂度大概是O(n^2/w)

然后卡着过去了。。。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <bitset>
using namespace std;
inline int read(){
    int k=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
    return k*f;
}
inline void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
    write(x);puts("");
}
struct ppap{int op,x,y;}q[100010];
bitset<20010>r[110],ans;
int n,m,a[100010],b[100010],p[100010];
int k[110][20010];
int main()
{
    n=read();m=read();
    int P=sqrt(n);
    for(int i=1;i<=n;i++){
        a[i]=b[i]=read();
        p[i]=(i-1)/P+1;
    }
    int cnt=n;
    for(int i=1;i<=m;i++){
        char c[5];scanf("%s",c);
        q[i].op=(c[0]=='R');
        q[i].x=read();q[i].y=read();
        if(q[i].op)b[++cnt]=q[i].y;
    }
    sort(b+1,b+cnt+1);cnt=unique(b+1,b+cnt+1)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
        k[p[i]][a[i]]++;if(k[p[i]][a[i]]==1)r[p[i]][a[i]]=1;
    }
    for(int i=1;i<=m;i++){
        int x=q[i].x,y=q[i].y;
        if(q[i].op){
            y=lower_bound(b+1,b+cnt+1,y)-b;
            k[p[x]][a[x]]--;if(k[p[x]][a[x]]==0)r[p[x]][a[x]]=0;
            a[x]=y;k[p[x]][y]++;if(k[p[x]][y]==1)r[p[x]][y]=1;
        }else{
            ans.reset();
            for(int j=p[x]+1;j<p[y];j++)ans|=r[j];
            for(int j=x;p[j]==p[x]&&j<=y;j++)ans[a[j]]=1;
            for(int j=y;p[j]==p[y]&&j>=x;j--)ans[a[j]]=1;
            writeln(ans.count());
        }
    }
    return 0;
}