BZOJ 2821 作诗(Poetize)

标签: bzojdecompositiondata-structure

题意

给定一个长度为 的序列 ,每次询问区间 中出现了正偶数次的数的个数。

解析

表示从前 块中 的出现个数,可以 预处理。令 表示从第 块到第 块的答案,也可以 预处理。

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

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);
	}
}