BZOJ2821 作诗 <分块>

Problem

作诗

Description

神犇虐完之后给傻X出了一题：
是T国的公主，平时的一大爱好是作诗。由于时间紧迫，作完诗之后还要虐，于是找来一篇长度为的文章，阅读次，每次只阅读其中连续的一段，从这一段中选出一些汉字构成诗。
因为喜欢对偶，所以规定最后选出的每个汉字都必须在里出现了正偶数次。而且认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是请安排选法。这种傻X当然不会了，于是向你请教……
问题简述：个数，组询问，每次问中有多少个数出现正偶数次。

Input

输入第一行三个整数，表示文章字数、汉字的种类数、要选择次。
第二行有个整数，每个数在间，代表一个编码为的汉字。
接下来行每行两个整数和，设上一个询问的答案为(第一个询问时)，令, ，若，交换和，则本次询问为。

Output

输出共行，每行一个整数，第个数表示第次能选出的汉字的最多种类数。

Sample Input

5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

Sample Output

2
0
0
0
1

Hint

对于的数据，

Source

By lydrainbowcat

标签：分块

Solution

由于”出现次数为偶数“不好维护，需要分块。
将序列分为个块，预处理出前块内每个数的出现次数，以及两块间的有多少个数出现偶数次。对于每个询问，将左右端点所在块中间的块有多少个数出现偶数次作为基础答案，然后暴力枚举块外的数，结合预处理出的“前块内每个数的出现次数”判断其对答案的影响即可。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
const int MAGIC = 316;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, c, m, a[MAX_N+5], buk[MAX_N+5];
int num[MAGIC+5][MAX_N+5], cnt[MAGIC+5][MAGIC+5];
int block(int p) {return p/MAGIC+1;}
int L(int num) {return max((num-1)*MAGIC, 1);}
int R(int num) {return min(num*MAGIC-1, n);}
int main() {
    read(n), read(c), read(m);
    for (int i = 1; i <= n; i++)
        read(a[i]), num[block(i)][a[i]]++;
    for (int i = 2; i <= block(n); i++)
        for (int j = 1; j <= c; j++)
            num[i][j] += num[i-1][j];
    for (int i = 1, t; i <= block(n); i++) {
        memset(buk, 0, sizeof buk), t = 0;
        for (int j = i; j <= block(n); cnt[i][j++] = t)
            for (int p = L(j); p <= R(j); buk[a[p++]]++)
                if (buk[a[p]]&1) t++;
                else if (buk[a[p]]) t--;
    }
    memset(buk, 0, sizeof buk);
    for (int l, r, ans = 0; m; m--) {
        read(l), read(r);
        l = (l+ans)%n+1, r = (r+ans)%n+1;
        if (l > r) swap(l, r); ans = 0;
        if (block(r)-block(l) <= 1) {
            for (int i = l; i <= r; buk[a[i++]]++)
                if (buk[a[i]]&1) ans++;
                else if (buk[a[i]]) ans--;
            for (int i = l; i <= r; i++) buk[a[i]]--;
        } else {
            ans = cnt[block(l)+1][block(r)-1];
            for (int i = l; i <= R(block(l)); i++) buk[a[i]]++;
            for (int i = r; i >= L(block(r)); i--) buk[a[i]]++;
            for (int i = l; i <= R(block(l)); buk[a[i++]] = 0)
                if (buk[a[i]]) {
                    int t = num[block(r)-1][a[i]]-num[block(l)][a[i]];
                    if (!t) ans += ((buk[a[i]]&1) == 0);
                    else if ((t&1) && (buk[a[i]]&1)) ans++;
                    else if (!(t&1) && (buk[a[i]]&1)) ans--;
                }
            for (int i = r; i >= L(block(r)); buk[a[i--]] = 0)
                if (buk[a[i]]) {
                    int t = num[block(r)-1][a[i]]-num[block(l)][a[i]];
                    if (!t) ans += ((buk[a[i]]&1) == 0);
                    else if ((t&1) && (buk[a[i]]&1)) ans++;
                    else if (!(t&1) && (buk[a[i]]&1)) ans--;
                }
        }
        printf("%d\n", ans);
    }
    return 0;
}