BZOJ2821 作诗 <分块>

Posted on Symbols count in article: 1k Reading time ≈ 4 mins.

Problem

作诗

Time  Limit:  50  Sec\mathrm{Time\;Limit:\;50\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

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

Input

输入第一行三个整数n,c,mn,c,m，表示文章字数、汉字的种类数、要选择MM次。
第二行有nn个整数，每个数AiA_i在[1,c][1, c]间，代表一个编码为AiA_i的汉字。
接下来mm行每行两个整数ll和rr，设上一个询问的答案为ansans(第一个询问时ans=0ans=0)，令L=(l+ans)mod  n+1L=(l+ans)\mod{n+1}, R=(r+ans)mod  n+1R=(r+ans)\mod{n+1}，若L>RL>R，交换LL和RR，则本次询问为[L,R][L,R]。

Output

输出共mm行，每行一个整数，第ii个数表示SHY\mathrm{SHY}第ii次能选出的汉字的最多种类数。

Sample Input

1
2
3
4
5
6
7
5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

Sample Output

1
2
3
4
5
2
0
0
0
1

Hint

对于100%100\%的数据，1≤n,c,m≤1051\le n,c,m\le10^5

Source

By lydrainbowcat

标签：分块

Solution

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}