题目描述

给定一个序列 $a_{[1,n]}$ 和 $m$ 次询问，每次询问给出 $l,r$，问 $[l,r]$ 中有多少个不同的数出现了偶数次。$n,m \leq 10^5$。

输入样例

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

输出样例

2
0
0
0
1

算法

(分块) $O(n\sqrt{n})$

将原序列分为 $\sqrt n$ 个块，可以枚举每一个块，从该块的左端点暴力向右枚举，在 $O(\sqrt n)$ 的复杂度内预处理出第 $i$ 个块到第 $j$ 个块的答案。

同时预处理一个数组 $s_{i,j}$，表示第 $i$ 个块的左端点到 $n$ 中 $j$ 出现的次数。同样可以暴力预处理，复杂度 $O(n \sqrt n)$。

然后每一次询问直接枚举零散块并考虑贡献即可。

时间 $O(n\sqrt n)$，空间 $O(n \sqrt n)$。

直接搞会被卡空间，可以把块长稍微调大一点。

C++ 代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

const int S = 400, N = 100005;
int n, m, c, suf[N / S + 5][N], a[N], blkans[N / S + 5][N / S + 5], cnt[N], pos[N];

inline void Read() {
    n = qread(); c = qread(); m = qread();
    for (register int i = 1;i <= n;i++) a[i] = qread(), pos[i] = (i - 1) / S + 1;
}

inline int Bl(int i) {return (i - 1) * S + 1;}
inline int Br(int i) {return Min(i * S, n);}

inline void Prefix() {
    for (register int i = 1;i <= pos[n];i++) {
        memset(cnt, 0, sizeof(cnt));
        register int curv = 0;
        for (register int j = Bl(i);j <= n;j++) {
            cnt[a[j]]++;
            if (cnt[a[j]] != 1 && (cnt[a[j]] & 1)) curv--;
            if (!(cnt[a[j]] & 1)) curv++;
            blkans[i][pos[j]] = curv;
        }
    }
    for (register int i = n;i >= 1;i--) {
        if (i < n && pos[i] != pos[i + 1]) {
            for (register int j = 1;j <= c;j++) suf[pos[i]][j] = suf[pos[i + 1]][j];
        }
        suf[pos[i]][a[i]]++;
    }
}

inline int Query(int l, int r, int v) {
    return suf[l][v] - suf[r + 1][v];
}

inline void Solve() {
    memset(cnt, 0, sizeof(cnt));
    int ans = 0;
    for (register int i = 1;i <= m;i++) {
        register int l = qread(), r = qread();
        l = (l + ans) % n + 1;
        r = (r + ans) % n + 1;
        if (l > r) l ^= r, r ^= l, l ^= r;
        if (pos[r] - pos[l] <= 1) {
            ans = 0;
            for (register int j = l;j <= r;j++) {
                cnt[a[j]]++;
                if (cnt[a[j]] != 1 && (cnt[a[j]] & 1)) ans--;
                if (!(cnt[a[j]] & 1)) ans++;
            }
            printf("%d\n", ans);
            for (register int j = l;j <= r;j++) cnt[a[j]]--;
        } else {
            ans = blkans[pos[l] + 1][pos[r] - 1];
            for (register int j = l;j <= Br(pos[l]);j++) {
                cnt[a[j]]++;
                if (cnt[a[j]] + Query(pos[l] + 1, pos[r] - 1, a[j]) == 1) continue;
                if ((cnt[a[j]] + Query(pos[l] + 1, pos[r] - 1, a[j])) & 1) ans--;
                else ans++;
            }
            for (register int j = Bl(pos[r]);j <= r;j++) {
                cnt[a[j]]++;
                if (cnt[a[j]] + Query(pos[l] + 1, pos[r] - 1, a[j]) == 1) continue;
                if ((cnt[a[j]] + Query(pos[l] + 1, pos[r] - 1, a[j])) & 1) ans--;
                else ans++;
            }
            printf("%d\n", ans);
            for (register int j = l;j <= Br(pos[l]);j++) cnt[a[j]]--;
            for (register int j = Bl(pos[r]);j <= r;j++) cnt[a[j]]--;
        }
    }
}

int main() {
    Read();
    Prefix();
    Solve();
    #ifndef ONLINE_JUDGE
    while (1);
    #endif
    return 0;
}