【CF1142B】Lynyrd Skynyrd

题面

洛谷

题解

假设区间\([l,r]\)内有一个循环位移，那么这个循环位移一定有一个最后的点，而这个点在循环位移中再往前移\(n-1\)个位置也一定在这个区间中。

那么我们将每一个点在它所在循环位移中前挪\(n-1\)个位置记下来，判断一下\([l,r]\)中是否有\(\geq l\)的点即可(具体实现详见代码)。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int MAX_N = 2e5 + 5;

int N, M, Q;

int a[MAX_N], p[MAX_N], tmp[MAX_N], nxt[18][MAX_N], pre[MAX_N];

int lg[MAX_N], st[18][MAX_N];

int query(int l, int r) {

	int t = lg[r - l + 1];

	return max(st[t][l], st[t][r - (1 << t) + 1]);

}

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	N = gi(), M = gi(), Q = gi();

	for (int i = 1; i <= N; i++) p[i] = gi();

	p[0] = p[N];

	for (int i = 1; i <= N; i++) pre[p[i]] = p[i - 1];

	for (int i = 1; i <= M; i++) a[i] = gi();

	for (int i = 1; i <= M; i++) nxt[0][i] = tmp[pre[a[i]]], tmp[a[i]] = i;

	for (int i = 2; i <= max(N, M); i++) lg[i] = lg[i >> 1] + 1;

	for (int i = 1; i <= lg[M]; i++)

		for (int j = 1; j <= M; j++)

			nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];

	for (int i = 1; i <= M; i++) {

		int pos = i;

		for (int j = 0; j <= lg[N - 1]; j++)

			if ((N - 1) >> j & 1) pos = nxt[j][pos];

		st[0][i] = pos;

	}

	for (int i = 1; i <= lg[M]; i++)

		for (int j = 1; j + (1 << i) - 1 <= M; j++)

			st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

	while (Q--) {

		int l = gi(), r = gi();

		if (query(l, r) >= l) putchar('1'); else putchar('0');

	}

	putchar('\n');

    return 0;

}