Codeforces ECR #029 : D. Yet Another Array Queries Problem

ここ1・2か月Codeforces系が妙にグダグダ。
http://codeforces.com/contest/863/problem/D

問題

N要素の数列Aに対し、以下の種類のクエリQ個を順に実行したとする。

• 部分列A[L...R]は1要素ローテーションする
• 部分列A[L...R]を反転する

indexがM個渡されるので、クエリ実行後各indexの値を答えよ。

解法

Mが小さいことに着目しよう。
M個の各indexに対し、クエリを逆順に巻き戻していき、もともとAのどの要素にあったものかを求めていけばO(MQ)で求められる。

int N,Q,M;
int A[202020];
int T[202020],L[202020],R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&Q,&M);
	FOR(i,N) scanf("%d",&A[i+1]);
	FOR(i,Q) scanf("%d%d%d",&T[Q-1-i],&L[Q-1-i],&R[Q-1-i]);
	FOR(i,M) {
		scanf("%d",&x);
		FOR(j,Q) {
			if(L[j]<=x && x<=R[j]) {
				if(T[j]==1) {
					x--;
					if(x<L[j]) x=R[j];
				}
				else {
					x=L[j]+R[j]-x;
				}
			}
		}
		_P("%d%c",A[x],(i==M-1)?'\n':' ');
	}
	
}

まとめ

巻き戻しに気が付けば簡単。