【ybt金牌導航6-3-3】【luogu P4135】偶數個數 / 作詩（分塊）

偶數個數 / 作詩

題目連結：ybt金牌導航6-3-3 / luogu P4135

題目大意

給你一個數組，多次詢問。

每次問你數組的一個區間中，有多少個數的出現次數是正偶數次。

思路

首先如果沒有線上，不難看出可以用莫隊。

但要線上，那我們考慮用分塊。

不難統計出 a n i , j an_{i,j} ani,j​ 為塊 i ∼ j i\sim j i∼j 的答案， n u m i , j num_{i,j} numi,j​ 為前 i i i 塊有多少個 j j j 這個數（字首和搞）。

那然後就直接整塊的答案為起點，然後放兩邊的進去。（記得判斷個數的時候要加上整塊的個數）

至于怎麼看答案加減，就是看加完之後那個數的個數，如果加完之後是偶數，答案就加一。（肯定不會是 0 0 0）

如果是奇數，而且個數大于 2 2 2，那答案就減一。（要大于 2 2 2 是因為小于 2 2 2 的時候原本還是 0 0 0）

然後記得搞完之後個數要減回去，不要 memset。

代碼

#include<cmath>
#include<cstdio>
#include<algorithm>

using namespace std;

int n, c, m, a[100001], ans, l, r, S;
int bl[401], br[401], s, num[401][100001], an[401][401];
int tmp[100001];

void premake() {
	for (int i = 1; i <= n; i++) {
		if (i % S == 1) {
			br[s] = i - 1;
			bl[++s] = i;
		}
		num[s][a[i]]++;//求每個塊中某個數出現多少次
	}
	br[s] = n;
	bl[s + 1] = br[s + 1] = n + 1;
	
	for (int i = 1; i <= c; i++)
		for (int j = 1; j <= s; j++)
			num[j][i] += num[j - 1][i];//字首和（1~j個塊中某個數出現次數）
	
	for (int i = 1; i <= s; i++) {//求 i~x 個塊的答案
		int now = 0;
		for (int j = bl[i]; j <= n; j++) {
			tmp[a[j]]++;
			if (!(tmp[a[j]] & 1)) now++;//新的正偶數出現了
				else if (tmp[a[j]] > 2) now--;//一個正偶數沒掉了
			an[i][(j - 1) / S + 1] = now;
		}
		for (int j = bl[i]; j <= n; j++)
			tmp[a[j]]--;//清空數組
	}
}

int work(int l, int r) {
	int L = (l - 1) / S + 1, R = (r - 1) / S + 1;
	int ans = 0;
	
	if (r - l + 1 <= 2 * S) {//直接暴力算
		for (int i = l; i <= r; i++) {
			tmp[a[i]]++;
			if (!(tmp[a[i]] & 1)) ans++;
				else if (tmp[a[i]] > 2) ans--;
		}
		for (int i = l; i <= r; i++)
			tmp[a[i]]--;
		return ans;
	}
	
	if (l == bl[L]) L--;
	if (r == br[R]) R++;
	ans = an[L + 1][R - 1];//一開始整塊有的答案
	for (int i = l; i <= br[L]; i++) {
		tmp[a[i]]++;
		int now = tmp[a[i]] + num[R - 1][a[i]] - num[L][a[i]];//記得加上整塊中的（後面也是）
		if (!(now & 1)) ans++;
			else if (now > 2) ans--;
	}
	for (int i = bl[R]; i <= r; i++) {
		tmp[a[i]]++;
		int now = tmp[a[i]] + num[R - 1][a[i]] - num[L][a[i]];
		if (!(now & 1)) ans++;
			else if (now > 2) ans--;
	}
	
	for (int i = l; i <= br[L]; i++) tmp[a[i]]--;//記得清空
	for (int i = bl[R]; i <= r; i++) tmp[a[i]]--;
	
	return ans;
}

int main() {
	scanf("%d %d %d", &n, &c, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	S = sqrt(n);
	premake();
	
	while (m--) {
		scanf("%d %d", &l, &r);
		l = (l + ans) % n + 1;
		r = (r + ans) % n + 1;
		if (l > r) swap(l, r);
		ans = work(l, r);
		printf("%d\n", ans);
	}
	
	return 0;
}