自动搬运

查看原文

来自洛谷，原作者为

	i207M 这个家伙很蠢，什么也没有留下

搬运于2025-08-24 21:56:52，当前版本为作者最后更新于2018-07-31 22:36:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次。

c的作用？？？

纪念一下自己YY出的一道分块水题

方法

其实这题就是在预处理时难住我了，如何保证$O(N\sqrt{N})$内预处理完？

$cnt[i][j]$表示第i块开始到结尾，j的出现次数；

$f[i][j]$表示i块开头到j块末尾的答案；

	for (ri i = 1; i <= bl[n]; ++i) {
		int t = 0;
		for (ri j = l[i]; j <= n; ++j) {
			cnt[i][a[j]]++;
			if ((cnt[i][a[j]] & 1) && (cnt[i][a[j]] > 1)) t--;
			else if ((cnt[i][a[j]] & 1) == 0) t++;
			if (bl[j] != bl[j + 1]) {
				f[i][bl[j]] = t;
			}
		}
	}

重点在于，不能先处理好每个块的答案，然后再枚举合并求出$f[i][j]$，不然复杂度爆炸，必须一边扫一边求；

然后统计就很好说了，分情况讨论即可；

注意ans的初值为f[bl[ql] + 1][bl[qr] - 1]；

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<bitset>
#include<deque>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
il char gc() {
	static const int BS = 1 << 22;
	static unsigned char buf[BS], *st, *ed;
	if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);
	return st == ed ? EOF : *st++;
}
#define gc getchar
template<class T>void in(T &x) {
	x = 0;
	bool f = 0;
	char c = gc();
	while (c < '0' || c > '9') {
		if (c == '-') f = 1;
		c = gc();
	}
	while ('0' <= c && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = gc();
	}
	if (f) x = -x;
}
#undef gc
#define pb push_back
#define N 100010
#define B 320
int n, m;
int a[N];
int block, bl[N];
int l[B];
int f[B][B];
int cnt[B][N];
int st[N], top;
int num[N];
// bitset<N>h[B][B], tmp;
signed main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
#endif
	int ans = 0, cc, ql, qr;
	in(n), in(cc), in(m);
	block = sqrt(n);
	for (ri i = 1; i <= n; ++i) {
		in(a[i]);
		bl[i] = (i - 1) / block + 1;
		if (bl[i] != bl[i - 1]) l[bl[i]] = i;
	}
	bl[n + 1] = bl[n] + 1;
	l[bl[n + 1]] = n + 1;
	for (ri i = 1; i <= bl[n]; ++i) {
		int t = 0;
		for (ri j = l[i]; j <= n; ++j) {
			cnt[i][a[j]]++;
			if ((cnt[i][a[j]] & 1) && (cnt[i][a[j]] > 1)) t--;
			else if ((cnt[i][a[j]] & 1) == 0) t++;
			if (bl[j] != bl[j + 1]) {
				f[i][bl[j]] = t;
			}
		}
	}
	while (m--) {
		in(ql), in(qr);
		ql = (ql + ans) % n + 1, qr = (qr + ans) % n + 1;
		if (ql > qr) swap(ql, qr);
		ans = 0;
		if (bl[ql] == bl[qr]) {
			for (ri i = ql; i <= qr; ++i) {
				num[a[i]]++;
				st[++top] = a[i];
			}
			while (top) {
				if (num[st[top]] != 0) {
					ans += (num[st[top]] & 1) ^ 1;
					num[st[top]] = 0;
				}
				top--;
			}
			printf("%d\n", ans);
			continue;
		}
		if (bl[ql] + 1 <= bl[qr] - 1) ans = f[bl[ql] + 1][bl[qr] - 1];
		for (ri i = ql; i < l[bl[ql] + 1]; ++i) {
			num[a[i]]++;
			st[++top] = a[i];
		}
		for (ri i = l[bl[qr]]; i <= qr; ++i) {
			num[a[i]]++;
			st[++top] = a[i];
		}
		while (top) {
			int t = st[top];
			if (num[t] != 0) {
				if ((cnt[bl[ql] + 1][t] - cnt[bl[qr]][t] > 0) && ((cnt[bl[ql] + 1][t] - cnt[bl[qr]][t]) & 1) == 0 && (num[st[top]] & 1)) {
					ans--;
				}
				else if (((cnt[bl[ql] + 1][t] - cnt[bl[qr]][t] > 0) && ((cnt[bl[ql] + 1][t] - cnt[bl[qr]][t]) & 1)) && (num[st[top]] & 1)) {
					ans++;
				}
				else if ((cnt[bl[ql] + 1][t] - cnt[bl[qr]][t] == 0) && (num[st[top]] & 1) == 0) {
					ans++;
				}
				num[st[top]] = 0;
			}
			top--;
		}
		printf("%d\n", ans);
	}
	return 0;
}