P3939 数颜色
$vecotr$里二分就是好用,全是$STL$
颜色数目比较少,可以对每一种颜色弄一个$vector$记录一下,查找$l,r$内颜色数为$x$的兔子数,直接在$G[x]$这个$vector$里二分即可
交换两个数。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define N 320202
using namespace std;
vector<int>G[N];
int n,m,c[N];
int main()
{
scanf("%d%d",&n,&m);
for(int x,i=1;i<=n;i++ ){
scanf("%d",&x);
G[x].push_back(i),c[i]=x;
}
for(int opt,l,r,x,i=1;i<=m;i++){
scanf("%d",&opt);
if(opt==1){
scanf("%d%d%d",&l,&r,&x);
int L=lower_bound(G[x].begin(),G[x].end(),l)-G[x].begin();
int R=upper_bound(G[x].begin(),G[x].end(),r)-G[x].begin()-1;
//>=l <=r
if(L>R) printf("0\n");
else printf("%d\n",R-L+1);
}else{
scanf("%d",&x);
if(c[x]==c[x+1]) continue;
l=x,r=x+1;
int pos_1=lower_bound(G[c[l]].begin(),G[c[l]].end(),l)-G[c[l]].begin();
int pos_2=lower_bound(G[c[r]].begin(),G[c[r]].end(),r)-G[c[r]].begin();
G[c[l]][pos_1]++;
G[c[r]][pos_2]--;
swap(c[x],c[x+1]);
}
}
return 0;
}
博主蒟蒻,若有出错的地方,敬请指出。
如有侵犯您版权的地方,请快速联系我,我会撤回本博文。