一、题意理解

给定长度为 $n$ 的序列 $a_1 \dots a_n$，$1 \le a_i \le c$。

$m$ 次询问区间 $[l,r]$ 中有多少种数字出现正偶数次。

强制在线：当前询问的 $l,r$ 由上一问答案 $ans$ 计算得到。

---

二、样例分析

输入：

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

数组：[1, 2, 2, 3, 1]

1. 第一次询问 $[0,4]$ → 实际 $[1,5]$ 整个数组：

   • 1出现2次（偶数）
   • 2出现2次（偶数）
   • 3出现1次（奇数） → 偶数次种类数 = 2（数字1和2）→ ans=2

2. 第二次：$l=1, r=2$，$ans=2$ → $L=(1+2)\%5+1=4$，$R=(2+2)\%5+1=5$ → $[4,5]$：

   • 数字3出现1次，数字1出现1次 → 偶数次种类数=0

3. 第三次：$l=2, r=2$，$ans=0$ → $L=(2+0)\%5+1=3$，$R=(2+0)\%5+1=3$ → $[3,3]$：

   • 数字2出现1次 → 偶数次种类数=0

4. 第四次：$l=2, r=3$，$ans=0$ → $L=(2+0)\%5+1=3$，$R=(3+0)\%5+1=4$ → $[3,4]$：

   • 数字2出现1次，数字3出现1次 → 偶数次种类数=0

5. 第五次：$l=3, r=5$，$ans=0$ → $L=(3+0)\%5+1=4$，$R=(5+0)\%5+1=1$ → 交换得 $[1,4]$：

   • 数字1出现1次，数字2出现2次，数字3出现1次 → 偶数次种类数=1（数字2）

输出：2 0 0 0 1

---

三、关键难点

• 强制在线 → 不能用莫队
• $n,m,c \le 10^5$，需要高效算法
• 询问区间出现偶数次的数字种类数

---

四、常见解法：分块

将序列分成 $\sqrt{n}$ 块，每块大小 $B \approx \sqrt{n}$。

预处理：

• $cnt[i][x]$：前 $i$ 块中数字 $x$ 的出现次数
• $f[i][j]$：第 $i$ 块到第 $j$ 块的答案（偶数次种类数）

---

1. 预处理 $cnt$

$cnt[i][x]$ 可以 $O(n\sqrt{n})$ 预处理。

2. 预处理 $f$

$f[i][j]$ 表示块 $i$ 到块 $j$ 的答案：

• 初始 $f[i][j] = f[i][j-1]$
• 加入第 $j$ 块，更新数字出现次数的奇偶性

复杂度 $O(n\sqrt{n})$

---

3. 回答询问

对于询问 $[L,R]$：

• 找到 $L$ 所在块 $b_l$，$R$ 所在块 $b_r$
• 如果 $b_l = b_r$，暴力计算 $O(B)$
• 否则：
  • 答案初始为 $f[b_l+1][b_r-1]$
  • 加入左边残块和右边残块，更新数字出现次数奇偶性
  • 用 $cnt$ 数组快速得到整块中出现次数，结合残块更新

复杂度 $O(\sqrt{n})$ 每次询问。

---

五、奇偶性维护技巧

我们只关心每个数字出现次数的奇偶性，可以用一个 bitset 或 int 位压缩来记录。

但 $c \le 10^5$，bitset 大小 $10^5$ 位，可以接受。

---

六、算法步骤

1. 分块，块大小 $B=\sqrt{n}$
2. 预处理 $cnt$ 数组
3. 预处理 $f$ 数组
4. 对每个询问：
   • 根据上次答案计算真实 $L,R$
   • 用分块方法求区间偶数次种类数
   • 输出答案

---

七、代码框架（C++）

#include <bits/stdc++.h>
using namespace std;
int a[100010], l[410], r[410], cnt[410][100010], n, c, m;
short b[100010], f[100010], ans[410][410], num, len;
int query(int ql, int qr) {
    int anss = 0;

    if (b[ql] + 1 >= b[qr]) {
        for (int i = ql; i <= qr; i++) {
            f[a[i]]++;

            if (f[a[i]] & 1)
                anss -= (f[a[i]] >= 3);
            else
                anss++;
        }

        for (int i = ql; i <= qr; i++)
            f[a[i]]--;
    } else {
        int pl = b[ql] + 1, pr = b[qr] - 1;
        anss = ans[pl][pr];

        for (int i = ql; i < l[pl]; i++)
            f[a[i]] = cnt[pr][a[i]] - cnt[pl - 1][a[i]];

        for (int i = r[pr] + 1; i <= qr; i++)
            f[a[i]] = cnt[pr][a[i]] - cnt[pl - 1][a[i]];

        for (int i = ql; i < l[pl]; i++) {
            f[a[i]]++;

            if (f[a[i]] & 1)
                anss -= (f[a[i]] >= 3);
            else
                anss++;
        }

        for (int i = r[pr] + 1; i <= qr; i++) {
            f[a[i]]++;

            if (f[a[i]] & 1)
                anss -= (f[a[i]] >= 3);
            else
                anss++;
        }

        for (int i = ql; i < l[pl]; i++)
            f[a[i]] = 0;

        for (int i = r[pr] + 1; i <= qr; i++)
            f[a[i]] = 0;
    }

    return anss;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ql, qr, lans = 0;
    cin >> n >> c >> m;
    len = sqrt(n);
    num = (int)ceil(n * 1.0 / len);

    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i] = (i - 1) / len + 1, cnt[b[i]][a[i]]++;

    for (int i = 1; i <= num; i++)
        l[i] = r[i - 1] + 1, r[i] = min(n, l[i] + len - 1);

    for (int i = 1; i <= num; i++)
        for (int j = 0; j <= c; j++)
            cnt[i][j] += cnt[i - 1][j];

    for (int i = 1; i <= num; i++) {
        for (int j = i; j <= num; j++) {
            ans[i][j] = ans[i][j - 1];

            for (int k = l[j]; k <= r[j]; k++) {
                f[a[k]]++;

                if (f[a[k]] & 1)
                    ans[i][j] -= (f[a[k]] >= 3);
                else
                    ans[i][j]++;
            }
        }

        memset(f, 0, sizeof(f));
    }

    for (int i = 1; i <= m; i++) {
        cin >> ql >> qr;
        ql = (ql + lans) % n + 1;
        qr = (qr + lans) % n + 1;

        if (ql > qr)
            swap(ql, qr);

        cout << (lans = query(ql, qr)) << '\n';
    }

    return 0;
}

---

八、复杂度分析

• 预处理：$O(n\sqrt{n})$
• 每次询问：$O(\sqrt{n})$
• 总复杂度：$O((n+m)\sqrt{n})$，可过 $10^5$

---

九、总结

本题的关键在于：

1. 理解强制在线条件下的区间查询问题。
2. 使用分块算法平衡预处理和查询复杂度。
3. 维护每个数字出现次数的奇偶性来统计偶数次种类数。
4. 注意边界块的处理和临时数组的清空。