BZOJ 2821 作诗(Poetize)

標籤： bzojdecompositiondata-structure

题意

给定一个长度为 $n$ 的序列 $a$，每次询问区间 $[l, r]$ 中出现了正偶数次的数的个数。

• $1 \le a_i \le C$
• $1 \le n, C, q \le 10^5$

解析

令 $cnt(i, x)$ 表示从前 $i$ 块中 $x$ 的出现个数，可以 $O(n\sqrt{n})$ 预处理。令 $ans(i, j)$ 表示从第 $i$ 块到第 $j$ 块的答案，也可以 $O(n\sqrt{n})$ 预处理。

询问时，在整块的基础上累加，块内的答案已经预处理出，不用管。扫描边缘的散块，用一个 $exist$ 数组表示出现了多少次，再根据 $exist$ 和 $cnt$ 的和的奇偶性判断答案应该增加还是减少。单次询问 $O(\sqrt{n})$。

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

	std::vector<int> a(n);
	for (auto &i : a) {
		scanf("%d", &i);
		i--;
	}

	int block_size = std::sqrt(n);
	int block_cnt = (n + block_size - 1) / block_size;

	std::vector<std::vector<int>> cnt(block_cnt + 1, std::vector<int>(c));
	for (int i = 1; i <= block_cnt; i++) {
		cnt[i] = cnt[i - 1];
		for (int j = (i - 1) * block_size; j < n && j < i * block_size; j++) {
			cnt[i][a[j]]++;
		}
	}

	std::vector<std::vector<int>> ans(block_cnt + 1, std::vector<int>(block_cnt + 1));
	std::vector<int> exist(c);
	for (int i = 0; i <= block_cnt; i++) {
		int res = 0;
		ans[i][i] = 0;
		for (int j = i + 1; j <= block_cnt; j++) {
			for (int k = (j - 1) * block_size; k < n && k < j * block_size; k++) {
				if (exist[a[k]] % 2 == 1) {
					res++;
				}
				else if (exist[a[k]] != 0) {
					res--;
				}
				exist[a[k]]++;
			}
			ans[i][j] = res;
		}
		for (int j = i * block_size; j < n; j++) exist[a[j]] = 0;
	}

	int last_ans = 0;
	while (m--) {
		int l, r;
		scanf("%d%d", &l, &r);
		l = (l + last_ans) % n + 1;
		r = (r + last_ans) % n + 1;
		if (l > r) std::swap(l, r);
		l--;

		if (l / block_size == r / block_size) {
			int res = 0;
			for (int i = l; i < r; i++) {
				if (exist[a[i]] % 2 == 1) res++;
				else if (exist[a[i]] != 0) res--;
				exist[a[i]]++;
			}
			for (int i = l; i < r; i++) exist[a[i]] = 0;
			last_ans = res;
		} else {

			int lb = (l + block_size - 1) / block_size;
			int rb = r / block_size;
			int res = ans[lb][rb];
			for (int i = l; i < lb * block_size; i++) {
				int tot_exist = cnt[rb][a[i]] - cnt[lb][a[i]] + exist[a[i]];
				if (tot_exist % 2 == 1) res++;
				else if (tot_exist != 0) res--;
				exist[a[i]]++;
			}
			for (int i = rb * block_size; i < r; i++) {
				int tot_exist = cnt[rb][a[i]] - cnt[lb][a[i]] + exist[a[i]];
				if (tot_exist % 2 == 1) res++;
				else if (tot_exist != 0) res--;
				exist[a[i]]++;
			}
			for (int i = l; i < lb * block_size; i++) exist[a[i]] = 0;
			for (int i = rb * block_size; i < r; i++) exist[a[i]] = 0;

			last_ans = res;
		}
		printf("%d\n", last_ans);
	}
}