「Bzoj 2821」作诗(Poetize)(分块)

BZOJ 2821
题意:求区间内出现次数为正偶数的数字的个数。

老套路,这种能方便将点加入答案的题目,维护$s(i,j)$为$i$块到$j$块出现次数为正偶数的数的个数(块到块节约空间),然后整块就处理完了,不完整块就每个数查询一下这个数出现在整块的次数和$[l,r]$的次数,用奇偶性判断是否要增加/减少答案。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int key, n, c, m, ai[MAXN], bl[MAXN], blolen, tax[MAXN], s[1500][1500];
vector<int> hh[MAXN];
int cha(int v, int l, int r) {
return upper_bound(hh[v].begin(), hh[v].end(), r) - upper_bound(hh[v].begin(), hh[v].end(), l - 1);
}
int query(int l, int r) {
int ans = 0;
if (bl[l] == bl[r]) {
for (int i = l; i <= r; i++) {
tax[ai[i]]++;
if (tax[ai[i]] % 2 == 0) ans++;
else if (tax[ai[i]] % 2 == 1 && tax[ai[i]] != 1) ans--;
}
for (int i = l; i <= r; i++) tax[ai[i]] = 0;
} else {
ans = s[bl[l] + 1][bl[r] - 1];
for (int i = l; i <= bl[l] * blolen; i++) {
if (tax[ai[i]]) continue;
tax[ai[i]] = 1;
int lr = cha(ai[i], l, r), li = cha(ai[i], l, bl[l] * blolen) + cha(ai[i], (bl[r] - 1) * blolen + 1, r);
if (lr == li) {
if (lr != 0 && lr % 2 == 0) ans++;
continue;
}
if ((lr - li) % 2 == 0) {
if (lr % 2 == 1) ans--;
} else {
if (lr % 2 == 0) ans++;
}
}
for (int i = (bl[r] - 1) * blolen + 1; i <= r; i++) {
if (tax[ai[i]]) continue;
tax[ai[i]] = 1;
int lr = cha(ai[i], l, r), ir = cha(ai[i], l, bl[l] * blolen) + cha(ai[i], (bl[r] - 1) * blolen + 1, r);
if (lr == ir) {
if (lr != 0 && lr % 2 == 0) ans++;
continue;
}
if ((lr - ir) % 2 == 0) {
if (lr % 2 == 1) ans--;
} else {
if (lr % 2 == 0) ans++;
}
}
for (int i = l; i <= bl[l] * blolen; i++) tax[ai[i]] = 0;
for (int i = (bl[r] - 1) * blolen + 1; i <= r; i++) tax[ai[i]] = 0;
}
return ans;
}
void clean() {
}
int solve() {
clean(); blolen = sqrt((db)n / log2(n));
for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), bl[i] = (i - 1) / blolen + 1, hh[ai[i]].push_back(i);
bool f = n % blolen;
for (int i = 1; i <= n / blolen + f; i++) {
ms(tax, 0);
for (int j = i; j <= n / blolen + f; j++) {
int x = (j - 1) * blolen + 1;
s[i][j] = s[i][j - 1];
for (int k = x; k <= j * blolen; k++) {
tax[ai[k]]++;
if (tax[ai[k]] % 2 == 0) s[i][j]++;
else if (tax[ai[k]] % 2 == 1 && tax[ai[k]] != 1) s[i][j]--;
}
}
}
ms(tax, 0);
while (m--) {
int l, r; scanf("%d%d", &l, &r);
l = (l + key) % n + 1, r = (r + key) % n + 1; if (l > r) swap(l, r);
printf("%d\n", key = query(l, r));
}
return 0;
}
int main() {
scanf("%d%d%d", &n, &c, &m), solve();
return 0;
}
------ 本文结束 ------