Problem – L – Codeforces

题意：你有一个长为 $n$ 的 01 串，但是有些位置是问号。现在给定 $m$ 个限制，每个限制都表示某个区间是回文的，问有多少种把问号替换成 0 或者 1 的方案，使得所有限制都能被满足。

$n, m \le 3 \times 10^5$

首先有一个最简单的 $O(nm)$ 暴力，先开一个并查集，对每个限制都暴力把对应的位置合并，最后对每个连通块处理一下就行了。

考虑如何优化，首先把原序列反转之后拼在后面，限制就变成了两个区间相等。

可以用类似 ST 表的方法来搞，如果第 $k$ 层的 $i, j$ 在同一块，就表示从 $i$ 和 $j$ 开始的长为 $2^k$ 的区间是完全相同的。那么每个限制就可以拆成两个，连完之后从上往下一层层下传关系就行了。

时空复杂度都是 $O(n\log n)$，当然可以用离线搞成线性空间，但是没必要。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 300005, p = (int)1e9 + 7;

struct union_find {
	int f[maxn * 2];

	void init(int n) {
		for (int i = 1; i <= n; i++)
			f[i] = i;
	}

	int find(int x) {
		return f[x] == x ? x : (f[x] = find(f[x]));
	}

	void link(int x, int y) {
		x = find(x);
		y = find(y);

		f[x] = y;
	}
} ufs[25];

char s[maxn];
int c[maxn * 2];

int main() {

	int n, m;
	scanf("%d%d", &n, &m);

	for (int k = 0; k <= 20; k++)
		ufs[k].init(n * 2);

	scanf("%s", s + 1);

	for (int i = 1; i <= n; i++)
		ufs[0].link(i, n * 2 - i + 1);

	while (m--) {
		int l, r;
		scanf("%d%d", &l, &r);

		int k = 31 - __builtin_clz(r - l + 1);

		ufs[k].link(l, n * 2 - r + 1);
		ufs[k].link(r - (1 << k) + 1, n * 2 - (l + (1 << k) - 1) + 1);
	}

	for (int k = 20; k; k--) {
		for (int i = 1; i <= n * 2; i++)
			if (ufs[k].find(i) != i) {
				int j = ufs[k].find(i);

				ufs[k - 1].link(i, j);
				ufs[k - 1].link(i + (1 << (k - 1)), j + (1 << (k - 1)));
			}
	}

	memset(c, -1, sizeof(c));

	bool bad = false;

	for (int i = 1; i <= n; i++)
		if (s[i] != '?') {
			int val = s[i] - '0', j = ufs[0].find(i);

			// printf("i = %d  j = %d\n", i, j);
			
			if (~c[j] && c[j] != val)
				bad = true;
			
			c[j] = val;
		}
	
	int ans = 1;
	if (bad)
		ans = 0;
	else {
		for (int i = 1; i <= n * 2; i++)
			if (ufs[0].find(i) == i && c[i] == -1)
				(ans *= 2) %= p;
	}

	printf("%d\n", ans);

	return 0;
}