Codeforces #591 Div1 B. Sequence Sorting

これ系いつもLISが頭に思い浮かんで失敗するんだよね。
https://codeforces.com/contest/1240/problem/B

問題

整数列Aが与えられる。
この数列に対し以下の処理を繰り返し行い、Aを昇順にソートしたい。

• ある整数を選び、その値を持つ要素をすべてまとめて数列の先頭か末尾に移動する

最小で処理回数が何回か。

解法

まず値を座標圧縮しておく。
最長で連続して昇順に並んでいる箇所を残すことを考えよう。
そうするとそのような項目を数え上げることになる。
座標圧縮後、ある値の初出の位置より、1小さい値の最後の登場位置が左にあるなら、その２値は処理を行わなくても連続にすることができる。

int Q;
int N;
int A[303030];
int L[303030];
int R[303030];
int C[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>N;
		vector<int> V;
		
		FOR(i,N) {
			cin>>A[i];
			V.push_back(A[i]);
		}
		sort(ALL(V));
		V.erase(unique(ALL(V)),V.end());
		FOR(i,V.size()) {
			R[i]=C[i]=0;
			L[i]=1<<30;
		}
		FOR(i,N) {
			A[i]=lower_bound(ALL(V),A[i])-V.begin();
			R[A[i]]=i;
			L[A[i]]=min(L[A[i]],i);
		}
		
		int ma=0;
		FOR(i,N) if(L[A[i]]==i) {
			if(A[i]==0) C[A[i]]=0;
			else {
				if(R[A[i]-1]<i) C[A[i]]=C[A[i]-1]+1;
				else C[A[i]]=0;
			}
			ma=max(ma,C[A[i]]);
		}
		
		
		
		cout<<V.size()-(ma+1)<<endl;
	}
}

まとめ

前も似たような問題でLISに走って1ミスしたような。