题解 P3939 【数颜色】
「QQ红包」
2017-11-01 23:27:52
肯定有人学数据结构学傻了。直接用 vector记录每个颜色出现的位置，然后二分一下就好。
因为颜色的范围很小，都不用离散。
```cpp
#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;
}
```