Lynyrd Skynyrd [Codeforces Round #549 (Div. 1) B]

https://codeforces.com/contest/1142/problem/B

長さNの順列Pと、長さMの数列Aがある。
数列Aの要素は[1,N]である。
これについて以下のクエリに答える。
　
A[L,R]の部分列でvalidな部分列が存在するなら1, 存在しないなら0を答える。
valid ⇔ 順列Pを0回以上シフト（cyclic-shift）して得られる数列と等しい

1≦N,M,Q≦2*10^5

前提知識

• ダブリング

解説

https://codeforces.com/contest/1142/submission/52040056

A[L,R]の部分列でvalidなものがあるかの判定を考えると、シフトされた順列の先頭を全探索して、
貪欲に先頭から当てはめて行き、Rまでに順列を網羅できたらvalidなものがあると考えることができる。

例）P = [2 1 3] A=[1 2 3 1 2 3]

A[0]が先頭で考える
1:A[0] -> 3:A[2] -> 2:A[4]

A[1]が先頭で考える
2:A[1] -> 1:A[3] -> 3:A[5]

これを見ると順列を遷移関係として捉えている。
そして、N-1回遷移し終わった後のindexだけが判定に使われていると気づく。
ここから、以下のようにまとめて解く。
　
P[0]→P[1], P[1]→P[2], ..., P[N-1]→P[0]のように遷移関係を作る。
go[from] := 数fromの次の遷移先を指す
　
v[i] := M[i]を先頭としてvalidな順列を構築したときの最小の後尾
このv[i]を作るためにダブリングを使おう。
nxt[i][d] := M[i]から2^d回遷移したときのindex
これを使えば、v[i]はnxt[i][d]をlog(N)回ほど使えば求められる。
　
クエリはv[L]～v[R]の最小値がR以下であるかを確認すれば答えられる。
自分はこれにSparseTableを使っているが、Segtreeでも問題ない。

int N, M, Q, P[201010], A[201010];
int nxt[201010][20];
int go[201010], memo[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M >> Q;
	rep(i, 0, N) cin >> P[i];
	rep(i, 0, M) cin >> A[i];

	rep(i, 0, N) {
		int a = i;
		int b = (i + 1) % N;
		go[P[a]] = P[b];
	}

	rep(i, 0, M + 1) rep(d, 0, 20) nxt[i][d] = M;
	rep(i, 0, N + 1) memo[i] = M;
	rrep(i, M - 1, 0) {
		nxt[i][0] = memo[go[A[i]]];
		memo[A[i]] = i;
	}
	rep(d, 1, 20) rep(i, 0, M) nxt[i][d] = nxt[nxt[i][d - 1]][d - 1];

	SparseTable<int> st;
	vector<int> v;
	rep(i, 0, M) {
		int x = i;
		rep(d, 0, 20) if ((N-1) & (1 << d)) x = nxt[x][d];
		v.push_back(x);
	}
	st.init(v);
	//rep(i, 0, M) printf("%d ", v[i]); printf("\n");

	rep(q, 0, Q) {
		int L, R; cin >> L >> R; L--; R--;
		auto res = st.get(L, R + 1);
		if (res <= R) printf("1");
		else printf("0");
	}
	printf("\n");
}