Problem – H – Codeforces

题意：众所周知有一个经典的 popcount 串，它的第 $i$ 个位置（0-based）是 $i$ 的 popcount 的奇偶性。

现在给定若干区间 $[l_i, r_i]$，把 popcount 串对应区间截取出来之后拼接成一个询问串 $s$。

另外还会输入若干个模式串 $t_i$，要求统计每个 $t_i$ 在 $s$ 中出现了多少次。

首先关于 popcount 串有一个显而易见的性质，它可以通过迭代产生，假设最开始只有一个 $0$，每次迭代就是把整个串取反后拼接在原串后面。另外它也有递归性质，如果把某个串记为 $s$，那么从它开始迭代若干次之后的串实际上就是把 popcount 串的 $0$ 替换成 $s$，$1$ 替换成取反的 $s$。

回到题目，由于有多个模式串并且都是输入的，考虑建一个 AC 自动机，然后模拟读入询问串并在 AC 自动机上走的过程。

关于询问串，首先有一个很显然的性质是可以像线段树一样把 $[l_i, r_i]$ 拆成 $\log$ 个区间，这些区间要么是 popcount 串的长为 $2^k$ 的前缀，要么就是前缀取反。

于是利用 popcount 串的递归性质，就可以倍增预处理出从每个结点开始走 $2^k$ 步（要分是否取反两种情况）会走到哪个点，这样就可以模拟读入整个询问串了。

在模拟读入的过程中还需要给所有遍历到的结点打一个标记。实际上可以开一个 $\log$ 层的标记数组，在遍历的时候只打一个对应层的标记，最后再 $O(n\log n)$ 逐层下传直到最后一层。至于每个模式串的出现次数当然就是对应结点在 fail 树上的子树和。

这道题其实代码非常简单，但是不得不说做法有些巧妙，训练的时候没有想出来。实际上 popcount 串的性质非常美妙，在思考的时候可以多角度灵活利用性质。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 500005;

int ch[maxn][2], fail[maxn], trie_cnt;
int q[maxn];

int insert(const char *c) {
	int x = 0;
	while (*c) {
		if (!ch[x][*c - '0'])
			ch[x][*c - '0'] = ++trie_cnt;
		
		x = ch[x][*c++ - '0'];
	}

	return x;
}

void get_fail() {
	int head = 1, tail = 1;

	for (int c = 0; c < 2; c++)
		if (ch[0][c])
			q[tail++] = ch[0][c];
	
	while (head < tail) {
		int x = q[head++];

		for (int c = 0; c < 2; c++) {
			if (ch[x][c]) {
				fail[ch[x][c]] = ch[fail[x]][c];
				q[tail++] = ch[x][c];
			}
			else
				ch[x][c] = ch[fail[x]][c];
		}
	}
}

int dp[31][2][maxn];
long long tag[31][2][maxn], sum[maxn];

void solve(int l, int r, int s, int t, int rev, vector<pair<int, int> > &v) { // int, 0/1
	if (s <= l && t >= r) {
		v.emplace_back(__builtin_ctz(r - l + 1), rev);
		return;
	}

	int mid = (l + r) / 2;
	if (s <= mid)
		solve(l, mid, s, t, rev, v);
	if (t > mid)
		solve(mid + 1, r, s, t, rev ^ 1, v);
}

int id[maxn], l[maxn], r[maxn];

char str[maxn];

int main() {

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

	for (int i = 1; i <= n; i++)
		scanf("%d%d", &l[i], &r[i]);

	for (int i = 1; i <= m; i++) {
		scanf("%s", str);

		id[i] = insert(str);
		// printf("id[%d] = %d\n", i, id[i]);
	}

	get_fail();

	for (int i = 0; i <= trie_cnt; i++) {
		dp[0][0][i] = ch[i][0];
		dp[0][1][i] = ch[i][1];
	}

	for (int j = 1; j <= 30; j++)
		for (int i = 0; i <= trie_cnt; i++) {
			dp[j][0][i] = dp[j - 1][1][dp[j - 1][0][i]];
			dp[j][1][i] = dp[j - 1][0][dp[j - 1][1][i]];
		}

	constexpr int N = 1 << 30;

	int o = 0;

	for (int i = 1; i <= n; i++) {
		vector<pair<int, int> > v;
		solve(0, N - 1, l[i], r[i], 0, v);

		// printf("[%d, %d] -> ", l[i], r[i]);
		// for (auto [k, t] : v)
		// 	printf(" (%d, %d)", k, t);
		// printf("\n");

		for (auto [k, t] : v) {
			tag[k][t][o]++;
			o = dp[k][t][o];
		}
	}

	for (int j = 30; j; j--)
		for (int i = 0; i <= trie_cnt; i++) { // 0 -> 01
			tag[j - 1][0][i] += tag[j][0][i];
			tag[j - 1][1][dp[j - 1][0][i]] += tag[j][0][i];

			tag[j - 1][1][i] += tag[j][1][i]; // 1 -> 10
			tag[j - 1][0][dp[j - 1][1][i]] += tag[j][1][i];
		}
	
	for (int i = 0; i <= trie_cnt; i++) {
		sum[ch[i][0]] += tag[0][0][i];
		sum[ch[i][1]] += tag[0][1][i];
	}

	for (int i = trie_cnt; i; i--) {
		int x = q[i];
		sum[fail[x]] += sum[x];
	}

	for (int i = 1; i <= m; i++)
		printf("%lld\n", sum[id[i]]);

	return 0;
}