如题

思路和P4168蒲公英差不多

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

const int N = 1e5 + 7;

using namespace std;

int n, c, m, blo, tot, ans;

int a[N], b[N], tong[N], flag[N];

int f[407][407], s[407][N];//第i块到第j块中的偶数个数，前i块中a[j]出现的次数

inline int block(int x) {
	return (x - 1) / blo + 1; 
}

inline void init() {
	tot = (n - 1) / blo + 1;
	
	for (int i = 1; i <= tot; ++ i) {
		int down = blo * (i - 1) + 1, up = std :: min(blo * i, n);
		
		for (int j = down; j <= up; ++ j) s[i][a[j]] ++;
		for (int j = 1; j <= c; ++ j) s[i][j] += s[i - 1][j];
	}
	
		for (int i = 1; i <= tot; ++ i) {
		for (int j = i; j <= tot; ++ j) {
			int down = blo * (j - 1) + 1, up = std :: min(blo * j, n);
			
			f[i][j] = f[i][j - 1];
			
			for (int k = down; k <= up; ++ k) {
				int del = s[j][a[k]] - s[i - 1][a[k]];
				
				if (! (del & 1)) f[i][j] = f[i][j - 1] + 1;
			}
		}
	}
}

inline int query(int l, int r) {
	memset(tong, 0, sizeof(tong));
	memset(flag, 0, sizeof(flag));
	
	int res = 0;
	int bl = block(l), br = block(r);
	
	//cout << bl << " " << br << endl;
	
	if (br - bl <= 1) {
		for (int i = l; i <= r; ++ i) tong[a[i]] ++;
		
		for (int i = l; i <= r; ++ i)
			if (! (tong[a[i]] & 1) && ! flag[a[i]]) res ++, flag[a[i]] = 1;
		
		return res;
	}
	
	for (int i = l; i <= blo * bl; ++ i) tong[a[i]] ++;
	for (int i = blo * (br - 1) + 1; i <= r; ++ i) tong[a[i]] ++;
	
	res = f[bl + 1][br - 1];
	
	for (int i = l; i <= blo * bl; ++ i) {
		if (flag[a[i]]) continue;
		
		flag[a[i]] = 1;
		
		int del = s[br - 1][a[i]] - s[bl][a[i]];
		int num = tong[a[i]] + del;
		
		if (! (num & 1) && ((del & 1) || ! del) && num) res ++;
		if ((num & 1) && del && ! (del & 1)) res --;
		 
	}
	
	for (int i = bl * (br - 1) + 1; i <= r; ++ i) {
		if (flag[a[i]]) continue;
		
		flag[a[i]] = 1;
		
		int del = s[br - 1][a[i]] - s[bl][a[i]];
		int num = tong[a[i]] + del;
		
		if (! (num & 1) && ((del & 1) || ! del) && num) res ++;
		if ((num & 1) && del && ! (del & 1)) res --;
	}
	
	return res;
}

int main() {
	scanf("%d%d%d", &n, &c, &m);
	
	c = 0;
	blo = sqrt(n);
	
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		
		c = std :: max(c, a[i]);
	}
	
	init();
	
/*	cout << tot << endl;
	
	for (int i = 1; i <= tot; ++ i) {
		for (int j = 1; j <= c; ++ j)
			cout << std :: min(blo * i, n) << " " << s[i][j] << endl;
	}
	
	for (int i = 1; i <= tot; ++ i) {
		for (int j = i; j <= tot; ++ j)
			cout << blo * (i - 1) + 1 << " " << std :: min(blo * j, n) << " " << f[i][j] << endl;
	}*/

	for (int i = 1; i <= m; ++ i) {
		int l, r;
		
		scanf("%d%d", &l, &r);

		l = (l + ans) % n + 1, r = (r + ans) % n + 1;
		
		if (l > r) std :: swap(l, r);
		
		printf("%d\n", ans = query(l, r));
	}
}