题解 P3939 【数颜色】

「QQ红包」 · 2017-11-01 23:27:52 · 题解

肯定有人学数据结构学傻了。直接用 vector记录每个颜色出现的位置，然后二分一下就好。

因为颜色的范围很小，都不用离散。

#include<bits/stdc++.h>
using namespace std;
int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(s>='0'&&s<='9')
    {
        k=k*10+(s-'0');
        s=getchar();
    }
    return k*base;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        write(-x);
    }
    else
    {
        if(x/10)write(x/10);
        putchar(x%10+'0');
    }
}
const int maxn=3e5+100;
const int maxm=6e5+100;
int n,m,bj,X,Y,Z,p1,p2;
int a[maxn],ans;
int tong[maxn];
int t1[maxn],Max;
int    t[11][maxn*2];
vector<int> g[maxn];
bool f1,f2,f3,f4;
void xg(int i,int x,int d)//t[i][x]+=d;
{
    int s=x;
    while (s<=n)
    {
        t[i][s]+=d;
        s+=(s&(-s));
    }
    return;
}
int qh(int i,int x)
{
    int s=x,sum=0;
    while (s)
    {
        sum+=t[i][s];
        s-=(s&(-s));
    }
    return sum;
}
int main()
{
    n=read();m=read();
    f4=true;
    for (int i=1;i<=n;i++) 
    {
        a[i]=read();
        Max=max(a[i],Max);
        if (tong[a[i]]!=0) f4=false;
        if (f4) tong[a[i]]=i;
        t1[a[i]]++;//cnt
    }
    if (Max<=10) f2=true; else f2=false;
/*    if (n<=1000)//一千以内的 
    {
        while (m--)
        {
            bj=read();
            if (bj==1)
            {
                ans=0;
                X=read();Y=read();Z=read();
                for (int i=X;i<=Y;i++)
                    if (a[i]==Z) ans++;
                printf("%d\n",ans);
            } else
            {
                X=read();
                swap(a[X],a[X+1]);
            }
        }
        return 0;
    }
    if (f4)//每个颜色只出现了一次 
    {
        while (m--)
        {
            bj=read();
            if (bj==1)
            {
                X=read();Y=read();Z=read();
                if (X<=tong[Z]&&tong[Z]<=Y) printf("1\n"); else printf("0\n");
            } else
            { 
                X=read();
                //a[X],a[X+1];
                tong[a[X]]++;
                tong[a[X+1]]--;
                swap(a[X],a[X+1]);
            }
        }
        return 0;
    }
    if (f2)//颜色小于10种，顺便说一下，不要用什么树状数组，前缀和维护一下就好 
    {
        for (int i=1;i<=n;i++) xg(a[i],i,1);
        while (m--)
        {
            bj=read();
            if (bj==1)
            {
                X=read();Y=read();Z=read();
                ans=qh(Z,Y)-qh(Z,X-1);
                printf("%d\n",ans);
            } else
            {
                X=read();
                xg(a[X],X,-1);
                xg(a[X],X+1,1);
                xg(a[X+1],X+1,-1);
                xg(a[X+1],X,1);
                swap(a[X+1],a[X]);
            }
        }
        return 0;
    }*/
    //然后还有一个部分分：特殊性质1
    //这个如果r-l<=20，暴力这一部分，否则暴力l~l-1和r+1~n，然后用整个的出现次数减一下就好 
    for (int i=1;i<=n;i++) g[a[i]].push_back(i);
    while (m--)
    {
        bj=read();
        if (bj==1)
        {
            X=read();Y=read();Z=read();
            p1=lower_bound(g[Z].begin(),g[Z].end(),X)-g[Z].begin();//找第一个>=X的 
            p2=upper_bound(g[Z].begin(),g[Z].end(),Y)-g[Z].begin()-1;//找第一个<=Y的 
            if (p2<p1) printf("0\n"); //这个注意要判掉 
            else
            printf("%d\n",p2-p1+1);
        } else
        {
            X=read();
            if (a[X]==a[X+1]) continue;//修改，如果颜色相同不用改了 
            p1=lower_bound(g[a[X]].begin(),g[a[X]].end(),X)-g[a[X]].begin();
            g[a[X]][p1]++;
            p2=lower_bound(g[a[X+1]].begin(),g[a[X+1]].end(),X+1)-g[a[X+1]].begin();
            g[a[X+1]][p2]--;
            swap(a[X],a[X+1]);//记得换掉 
        }
    }
    return 0;
}