【题解】洛谷 P3939 数颜色【20201013 CSP 模拟赛】

题目链接

题目链接

题意

序列 \(c_i\)，维护以下两个操作：

• \(\operatorname{swap}(c_x,c_{x+1})\)；
• 查询 \(\sum_{i=l}^r[c_i==c]\)

\(n,c_i\leq 3\times 10^5\)，\(m\leq 6\times 10^5\)

题解

用 vector 维护每个颜色出现在哪些位置，查询时二分；修改时先二分到位置，\(O(1)\) 修改。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll getint(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*f;
}
const int N=3e5+10;
int pool[N<<2],*p=pool;
int *v[N],top[N];
int ccnt[N];
int col[N];
int main(){
	int n=getint(),m=getint();
	int cmax=0;
	for(int i=1;i<=n;i++)col[i]=getint(),cmax=max(cmax,col[i]),ccnt[col[i]]++;
	for(int i=1;i<=cmax;i++)v[i]=p,p+=ccnt[i]+2;
	for(int i=1;i<=cmax;i++)v[i][top[i]++]=-1;
	for(int i=1;i<=n;i++)v[col[i]][top[col[i]]++]=i;
//	for(int i=1;i<=cmax;i++)cerr<<". "<<v[i]-pool<<" "<<v[i]-pool+top[i]<<endl;
	while(m-->0){
		int tp=getint();
		if(tp==1){
			int l=getint(),r=getint(),c=getint();
			int ans=upper_bound(v[c],v[c]+top[c],r)
				   -lower_bound(v[c],v[c]+top[c],l);
			printf("%d\n",ans);
		}else{
			int x=getint();
			if(col[x]==col[x+1])continue;
			else{
				auto a=lower_bound(v[col[x]],v[col[x]]+top[col[x]],x),
					 b=lower_bound(v[col[x+1]],v[col[x+1]]+top[col[x+1]],x+1);
				++(*a);
				--(*b);
				swap(col[x],col[x+1]);
			}
		}
	}
	return 0;
}