2019.9.2アナログ試合B、数色(vectorの巧みな運用)

タイトル
https://www.luogu.org/problem/P3939
 
 
問題解
最初は1つの区間内の色の種類数を求めているのかと思ったら、修正もついていて、その場で呆然としていました...
その結果、1つの区間内のある色の個数を求めます...
これは裸ではありませんか?
データ範囲n<=300000
あれ、もっと速いアルゴリズムがあるのかな
あるらしい
各色にセットを付けて、各色の座標をどこに保存し、lower_boundで調べればいい
しかしsetはポイントの順位を調べることができません
そこでn個のvectorを用い,座標順に対応色のvectorを押し込む.
そしてlower_boundはランキングを調べました
2つの隣接する数を交換するのでvectorの中の相対的な順序は変わらない
各ポイントのposを保存することで、修正操作を完了できます.
コード:(書きやすい)

#include
#include
#include
#include
using namespace std;
inline int gi()
{
	char c;int num=0,flg=1;
	while((c=getchar())'9')if(c=='-')flg=-1;
	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
	return num*flg;
}
#define N 300005
vector b[N];
vector::iterator t1,t2;
int a[N],pos[N],siz[N];
int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	int n,m,i,l,r,c,x,op;
	n=gi();m=gi();
	for(i=1;i<=n;i++){
		a[i]=gi();
		b[a[i]].push_back(i);
		pos[i]=siz[a[i]];
		siz[a[i]]++;
	}
	for(i=1;i<=m;i++){
		op=gi();
		if(op==1){
			l=gi();r=gi();c=gi();
			if(siz[c]){
				t1=lower_bound(b[c].begin(),b[c].end(),l);
				t2=upper_bound(b[c].begin(),b[c].end(),r);
				t2--;
				printf("%d
",t2-t1+1);
			}
			else
				printf("0
");
		}
		if(op==2){
			x=gi();
			if(a[x]!=a[x+1]){
				b[a[x]][pos[x]]++;
				b[a[x+1]][pos[x+1]]--;
				swap(a[x],a[x+1]);
				swap(pos[x],pos[x+1]);
			}
		}
	}
}