「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;
}