[bzoj 2821] 作诗(Poetize)

题意: 长度为n的数列, m个询问, 每次问[l, r]中有多少个数出现正偶数次, 强制在线. (1<=n,c,m<=10^5)

据说shy是lyd的女票......嗯, lydshy.

hzwer说这题跟区间众数一样, 于是就去学习了区间众数问题, 还是不会. 原来我并没有领会其中的真谛: 设计这个算法的灵感从何而来?

合并两个区间, 每个数的出现次数变得很乱. 但是, 如果只是加入一个数, 一切都变得那么明了. 如果它以前出现了奇数次, 现在便出现正偶数次, 答案+1; 如果以前没出现, 答案不变; 如果以前出现了正偶数次, 答案-1. 回想一下区间众数: 如果它以前出现的次数+1大于原来众数的出现次数, 答案变成它; 反之, 答案不变. 虽然它们不具备最优子结构, 但是新加入一个数所带来的变化是可控的.

许多和 "出现次数" 有关的在线统计问题都能这样解决. 假设只问出现次数, 除了出现次数最多的数, 出现正偶数次的数, 还可以回答只出现一次的数 (也可以记录每种数左边最近的同类在哪里, 可持久化权值线段树), 出现次数最少的数 (维护出现各个次数的数有多少, 和莫队有点像).

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_N = 1e5, SIZE = 77, BLOCK = MAX_N/SIZE + 1;
int n, N, q, sz, blk, f[BLOCK][BLOCK], t[MAX_N], x[MAX_N];
vector<int> pos[MAX_N];

void init()
{
	sz = sqrt(n/log2(n));
	blk = (n+sz-1)/sz;
	for (int i = 0; i < blk; ++i) {
		int ans = 0;
		for (int j = i; j < blk; ++j) {
			for (int k = j*sz, l = min(n, k+sz); k < l; ++k) {
				int& y = t[x[k]];
				ans -= y && !(y & 1);
				ans += y & 1;
				++y;
			}
			f[i][j] = ans;
		}
		for (int j = i*sz; j < n; ++j)
			t[x[j]] = 0;
	}
}

inline int cnt(int a, int l, int r)
{
	return lower_bound(pos[a].begin(), pos[a].end(), r)
		- lower_bound(pos[a].begin(), pos[a].end(), l);
}

int query(int l, int r)
{
	static bool v[MAX_N];
	int lb = l/sz, rb = r/sz, ans = 0, i;
	if (lb == rb) {
		for (i = l; i <= r; ++i)
			++t[x[i]];
		for (i = l; i <= r; ++i) {
			ans += !(v[x[i]] || (t[x[i]] & 1));
			v[x[i]] = true;
		}
		for (i = l; i <= r; ++i) {
			t[x[i]] = 0;
			v[x[i]] = false;
		}
	} else {
		ans = rb-lb > 1 ? f[lb+1][rb-1] : 0;
		int st = (lb+1)*sz, ed = rb*sz, m = 0;
		static int s[MAX_N];
		for (i = l; i < st; ++i)
			s[m++] = x[i];
		for (i = ed; i <= r; ++i)
			s[m++] = x[i];
		for (i = 0; i < m; ++i) if (!v[s[i]]) {
			int c1 = cnt(s[i], st, ed), c2 = cnt(s[i], l, r+1);
			ans += !(c2 & 1) - (c1 && !(c1 & 1));
			v[s[i]] = true;
		}
		for (int i = 0; i < m; ++i)
			v[s[i]] = false;
	}
	return ans;
}

int main()
{
	scanf("%d %d %d", &n, &N, &q);
	for (int i = 0; i < n; ++i) {	
		scanf("%d", &x[i]);
		--x[i];
		pos[x[i]].push_back(i);
	}
	init();
	int ans = 0;
	while (q--) {
		int l, r;
		scanf("%d %d", &l, &r);
		l = (l + ans) % n;
		r = (r + ans) % n;
		if (l > r)
			swap(l, r);
		printf("%d\n", ans = query(l, r));
	}
	return 0;
}