Codeforces #879 : Div2 F. Typewriter

問題文を読むのに疲れる。
https://codeforces.com/contest/1834/problem/F

問題

1～Nの順列Pを、以下の装置を使って並べ替える。
初期状態でN個のセルがあり、i番目にはP[i]の値が格納されている。
カーソルが初期状態で1番のセルの前にある。

以下の処理を任意の順で行い、Pをソートせよ。

• カーソル位置のセルの値を、カーソルに拾い上げる。
• カーソル位置のセルの値を、カーソルに拾い上げたものにする。カーソルの中身は空になる。
• カーソル位置のセルの値と、カーソルの中身を交換する。
• カーソルの位置を、i番のセルからi+1番のセルに移動する。
• カーソルの位置を、1番のセルに戻す。

以下のクエリを行い、その都度Pのソートにかかる「カーソルの位置を、1番のセルに戻す」の最小回数を求めよ。

• Pを指定された数ローテートする
• Pを反転する

解法

先に、Pをローテートしたときの解を全部求めておこう。同様に、Pを反転したものについてもローテートしたときの解を求めておく。
1番のセルに戻る回数は、P[i]＜iであるようなiの個数である。
よってP[i]＜iが生じるローテート回数の範囲が定まるので、累積和の要領でそれらを加算しよう。

int N;
int A[402020];
int X[402020];
int Y[402020];
int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
	}
	FOR(i,N) {
		x=A[i];
		if(x<i) {
			X[0]++;
			X[i-x]--;
			X[i+1]++;
		}
		else {
			X[i+1]++;
			X[N-(x-i)]--;
		}
	}
	FOR(i,N) {
		x=A[N-1-i];
		if(x<i) {
			Y[0]++;
			Y[i-x]--;
			Y[i+1]++;
		}
		else {
			Y[i+1]++;
			Y[N-(x-i)]--;
		}
	}
	FOR(i,N) X[i+1]+=X[i],Y[i+1]+=Y[i];
	x=y=0;
	cout<<X[0]<<endl;
	
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1||i==2) {
			cin>>k;
			if(i==1) y+=N-k;
			if(i==2) y+=k;
			y%=N;
		}
		else {
			x^=1;
			y=N-1-y;
		}
		
		if(x==0) {
			cout<<X[(N-y)%N]<<endl;
		}
		else {
			cout<<Y[N-1-y]<<endl;
		}
	}
	
}

まとめ

3000pt問題の割には素直。