「CF1142B」Lynyrd Skynyrd

传送门

Luogu

解题思路

发现一个性质：

对于排列的任何一个循环位移，排列中的同一个数的前驱肯定是不变的。

而且，如果一个排列的循环位移是某一个区间的子序列，那么这个循环位移的结尾的 \(n-1\) 级前驱一定要位于这个区间内。

到这里我们就可以倍增维护 \(2^k\) 级祖先，然后再搞一个数据结构维护一下区间最大值就好了。

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

 	s = 0; int f = 0; char c = getchar();

 	while (!isdigit(c)) f |= (c == '-'), c = getchar();

 	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

 	s = f ? -s : s;

}

const int _ = 200010;

int n, m, q, p[_], pre[_], lg[_];

int a[_], las[_], f[22][_], st[22][_];

inline int query(int ql, int qr) {

	int x = lg[qr - ql + 1];

	return max(st[x][ql], st[x][qr - (1 << x) + 1]);

}

int main() {

#ifndef ONLINE_JUDGE

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

#endif

	read(n), read(m), read(q);

	for (rg int i = 2; i <= max(n, m); ++i) lg[i] = lg[i / 2] + 1;

	for (rg int i = 1; i <= n; ++i) read(p[i]); p[0] = p[n];

	for (rg int i = 1; i <= m; ++i) read(a[i]);

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

	for (rg int i = 1; i <= m; ++i) f[0][i] = las[pre[a[i]]], las[a[i]] = i;

	for (rg int j = 1; j <= lg[m]; ++j)

		for (rg int i = 1; i <= m; ++i)

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

	for (rg int i = 1; i <= m; ++i) {

		st[0][i] = i;

		for (rg int j = 0; j <= lg[n]; ++j)

			if ((n - 1) & (1 << j)) st[0][i] = f[j][st[0][i]];

	}

	for (rg int j = 1; j <= lg[m]; ++j)

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

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

	for (rg int ql, qr, i = 1; i <= q; ++i)

		read(ql), read(qr), putchar(query(ql ,qr) >= ql ? '1' : '0');

	return 0;

}

完结撒花 \(qwq\)

巴特西

「CF1142B」Lynyrd Skynyrd

解题思路

细节注意事项

参考代码

最新文章

热门文章