作诗 - 题目列表

形式化题目

给定长度为 $n$ 的序列 $A$ ，值域 $[1, c]$ ，以及 $m$ 个在线询问。每个询问给出区间 $[L, R]$ ，求 $A_L \dots A_R$ 中出现次数为正偶数（至少 2 次且次数为偶数）的数值种类数。

询问强制在线：设上一个答案为 $ans$ （初始为 0），本次读入 $l, r$ ，则

L = (l + ans) \bmod n + 1,\quad R = (r + ans) \bmod n + 1

若 $L > R$ 则交换。 $1 \leqslant n, c, m \leqslant 10^5$ 。

以样例 $A = [1, 2, 2, 3, 1]$ 为例，第一个询问 $[1, 5]$ ：值 1 出现 2 次、值 2 出现 2 次、值 3 出现 1 次，答案为 2。

正解

思路

朴素做法的瓶颈。 最直接的做法是每个询问开计数器扫一遍区间，单次 $O(n)$ 、总共 $O(nm) = 10^{10}$ ，必然超时。更麻烦的是询问强制在线：上一问的答案决定下一问的区间，一切依赖"询问顺序已知"的离线手法（莫队、按右端点排序的扫描线）都不可用。于是只剩一条路：预先算出与询问顺序无关的完整信息，让每个询问只补一小块——这正是分块的形状。

分块拆解。 取块长 $T$ （实现中取 1000），把位置每 $T$ 个分一块。任意区间 $[l, r]$ 都能拆成三段：

text

1
2[ l .. 块bl的末尾 | 完整块 bl+1 .. br-1 | 块br的开头 .. r ]
   左散段（<T 个）      中间完整块          右散段（<T 个）

完整块部分的答案可以用一张预处理表 $g[i][j]$ （块 $i$ 到块 $j$ 组成的区间中正偶数值的个数） $O(1)$ 拿到；两侧散段合计不到 $2T$ 个元素，只涉及 $\leqslant 2T$ 个互异值——对这批值做"补偿"，就能修正它们在 $g$ 中被算错或漏算的贡献。

预处理 $g[i][j]$ ：固定左端、右端扫描线增量。 枚举左端块 $i$ ，让右端块 $j$ 从 $i$ 向右扫，同时维护 $cnt[v]$ （值 $v$ 在块区间 $[i,j]$ 中的出现次数）和 $cur$ （当前正偶数值个数）。并入第 $j$ 块时，只有第 $j$ 块里出现过的值的计数会变，对每个这样的值计算状态函数

f(x) = [\,x \text{ 为正偶数}\,] = [\,x \geqslant 2 \text{ 且 } x \equiv 0 \pmod 2\,]

的新旧差 $\sum f(\text{after}) - \sum f(\text{before})$ ，累加进 $cur$ 即得 $g[i][j]$ 。全部行为 $O\!\left(\dfrac{n}{T} \cdot n\right)$ 次值级操作。

查询：散段二次补偿。 设中间完整块为 $[bl+1, br-1]$ 。先取两侧散段的互异值并集 $vu$ ，对其中每个值 $v$ 求两个数：

$tin[v]$ ： $v$ 在中间完整块 $bl+1 \dots br-1$ 中的次数（块计数的前缀和 $O(1)$ 查）；
$t[v]$ ： $v$ 在整个区间 $[l,r]$ 的次数 $= tin[v] +$ 左散段次数 $+$ 右散段次数。

则

ans = g[bl+1][br-1] + \sum_{v \in vu} f(t[v]) - \sum_{v \in vu} f(tin[v])

为什么恰好补对：完整块独有的值不在 $vu$ 里，它的 $f$ 值已经由 $g$ 正确计入，加减两项都不涉及它；散段里的每个互异值则被从状态 $f(tin)$ 修正成真实状态 $f(t)$ 。注意 $f(0) = 0$ ，所以只出现在散段里的值（ $tin = 0$ ）公式同样自洽。

Python 落地：把"逐值二分"变成"整组二分"。 上面每个散段值都要在序列里数出现次数，纯 Python 逐值二分太慢。把每个位置编码成一个键 $v \cdot (n+1) + pos$ 后整体排序，那么任取一组值，它们在位置区间 $[lo, hi)$ 中的出现总次数就是一次成对二分：

\texttt{searchsorted}(keys,\ vu\cdot(n{+}1)+hi) - \texttt{searchsorted}(keys,\ vu\cdot(n{+}1)+lo)

整组值一次性向量化算完，单次询问只剩 $O(T \log n)$ 级操作。

两个容易踩的坑（都曾在小样例上被掩盖）：

解密公式是 $(l + ans) \bmod n + 1$ ，转成 0 下标后等价于 $(l + ans) \bmod n$ ；写成 $\bmod\ (n+1)$ 再减一，样例都过不了。
中间完整块是 $bl+1 \dots br-1$ ，块 $br$ 本身是散块。 $tin$ 要用 $pre[br] - pre[bl+1]$ ， $g$ 取 $g[bl+1][br-1]$ ；如果把 $br$ 也当完整块，凡是 $r$ 不在块末尾就会多算。

代码

cpp

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 作诗：分块预处理「整块区间内出现正偶数次的数值个数」，询问补两端零散位置。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

typedef long long ll;

const ll T = 1000; // 分块大小

struct BlockVal {
    int v; // 值
    int c; // 该值在本块内的出现次数
};

int main() {
    ll n, c, m;
    if (scanf("%lld %lld %lld", &n, &c, &m) != 3) return 0; // 空输入安全返回
    std::vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    ll blocks = (n + T - 1) / T;
    ll W = c + 1;

    // pre[i][v] = 前 i 个块中值 v 的出现次数
    std::vector<int> pre((blocks + 1) * W, 0);
    std::vector<std::vector<BlockVal> > nz(blocks); // 每块里出现过的值与块内次数

    std::vector<int> cntB(c + 1, 0);
    std::vector<int> touched;
    for (ll i = 0; i < blocks; i++) {
        ll lo = i * T, hi = (i + 1) * T;
        if (hi > n) hi = n;
        touched.clear();
        for (ll t = lo; t < hi; t++) {
            int v = (int)a[t];
            if (cntB[v] == 0) touched.push_back(v);
            cntB[v]++;
        }
        memcpy(&pre[(i + 1) * W], &pre[i * W], W * sizeof(int)); // 先继承前缀
        for (size_t t = 0; t < touched.size(); t++) {
            int v = touched[t];
            pre[(i + 1) * W + v] += cntB[v];
            BlockVal bv;
            bv.v = v;
            bv.c = cntB[v]; // 块内计数不能只用「出现与否」
            nz[i].push_back(bv);
            cntB[v] = 0;
        }
    }

    // g[i][j] = 完整块区间 [i, j] 内出现正偶数次的数值个数
    std::vector<std::vector<int> > g(blocks, std::vector<int>(blocks, 0));
    std::vector<int> cnt(c + 1, 0);
    for (ll i = 0; i < blocks; i++) {
        touched.clear();
        ll cur = 0;
        for (ll j = i; j < blocks; j++) {
            for (size_t t = 0; t < nz[j].size(); t++) {
                int v = nz[j][t].v;
                ll before = cnt[v];
                ll after = before + nz[j][t].c;
                cnt[v] = (int)after;
                bool db = (before % 2 == 0 && before >= 2); // 状态函数 f(x) = (x 为正偶数)
                bool da = (after % 2 == 0 && after >= 2);
                if (da && !db) cur++;
                else if (!da && db) cur--;
                if (before == 0) touched.push_back(v);
            }
            g[i][j] = (int)cur;
        }
        for (size_t t = 0; t < touched.size(); t++) cnt[touched[t]] = 0;
    }

    std::vector<int> ccnt(c + 1, 0);
    std::vector<int> touch;
    ll ans = 0; // 上一个询问的答案，强制在线解密用
    for (ll q = 0; q < m; q++) {
        ll ql, qr;
        scanf("%lld %lld", &ql, &qr);
        ll l = (ql + ans) % n;
        ll r = (qr + ans) % n;
        if (l > r) {
            ll tmp = l; l = r; r = tmp;
        }
        ll bl = l / T, br = r / T;

        touch.clear();
        if (br - bl < 2) {
            // 中间没有完整块：整段当作散段直接统计
            for (ll i = l; i <= r; i++) {
                int v = (int)a[i];
                if (ccnt[v] == 0) touch.push_back(v);
                ccnt[v]++;
            }
            ll res = 0;
            for (size_t t = 0; t < touch.size(); t++) {
                ll cntv = ccnt[touch[t]];
                if (cntv >= 2 && cntv % 2 == 0) res++;
            }
            ans = res;
        } else {
            // 两侧散段的互异值：先在完整块答案上做补偿
            ll lhi = (bl + 1) * T;
            for (ll i = l; i < lhi; i++) {
                int v = (int)a[i];
                if (ccnt[v] == 0) touch.push_back(v);
                ccnt[v]++;
            }
            for (ll i = br * T; i <= r; i++) {
                int v = (int)a[i];
                if (ccnt[v] == 0) touch.push_back(v);
                ccnt[v]++;
            }
            ll res = g[bl + 1][br - 1];
            for (size_t t = 0; t < touch.size(); t++) {
                int v = touch[t];
                ll tin = pre[br * W + v] - pre[(bl + 1) * W + v]; // 该值在中间完整块的次数
                ll total = tin + ccnt[v];
                if (total >= 2 && total % 2 == 0) res++;      // 总次数为正偶数
                if (tin >= 2 && tin % 2 == 0) res--;          // 只在中间块里算成过正偶数
            }
            ans = res;
        }

        printf("%lld\n", ans);
        for (size_t t = 0; t < touch.size(); t++) ccnt[touch[t]] = 0;
    }
    return 0;
}

python

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 18:28
# update_at: 2026-10-01 18:28

import numpy as np
import sys

T = 1000  # 分块大小：位置按每 T 个分成一块，块内散元素 ≤ 2T 个逐个补偿


def block_pair_table(bc: np.ndarray, blocks: int) -> list[list[int]]:
    """g[i][j] = 完整块区间 [i, j] 内出现正偶数次的数值个数。

    逐行递增右端块：往 [i, j-1] 的计数里并入第 j 块，
    只有第 j 块里出现过的值状态可能变化，增量只在这些值上算。
    """
    g = [[0] * blocks for _ in range(blocks)]
    cnt = np.zeros(bc.shape[1], np.int32)  # 值 → 在块 [i, j] 中的出现次数
    for i in range(blocks):
        cnt[:] = 0
        cur = 0
        row = g[i]
        for j in range(i, blocks):
            nz = np.nonzero(bc[j])[0]          # 第 j 块里出现过的值
            before = cnt[nz]
            after = before + bc[j][nz]
            cnt[nz] = after
            # 状态函数 f(x) = (x 为正偶数)：新状态转 1、旧状态转 1，差值即增量
            cur += int((((after & 1) == 0) & (after >= 2)).sum()
                       - (((before & 1) == 0) & (before >= 2)).sum())
            row[j] = cur
    return g


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    nums = list(map(int, data))
    n, c, m = nums[0], nums[1], nums[2]
    a = np.array(nums[3:3 + n], dtype=np.int32)
    qs = nums[3 + n:]

    blocks = (n + T - 1) // T
    bc = np.zeros((blocks, c + 1), np.int32)  # 每块内各值的出现次数
    np.add.at(bc, (np.arange(n) // T, a), 1)
    pre = np.zeros((blocks + 1, c + 1), np.int32)  # pre[i][v] = 前 i 块中 v 的次数
    np.cumsum(bc, axis=0, out=pre[1:])

    # 把 (值, 位置) 编码成一个 int64 键后全局排序：值 v 在位置区间 [lo, hi]
    # 的出现次数 = 二分键 v*(n+1)+hi+1 与 v*(n+1)+lo 的差，可对整组值向量化
    keys = np.sort(a.astype(np.int64) * (n + 1) + np.arange(n, dtype=np.int64))
    g = block_pair_table(bc, blocks)

    out: list[str] = []
    ans = 0  # 上一个询问的答案，强制在线解密用
    n1 = n + 1
    for q in range(m):
        l = (qs[2 * q] + ans) % n           # 题面 L=(l+ans) mod n+1，转 0 下标后即 mod n
        r = (qs[2 * q + 1] + ans) % n
        if l > r:
            l, r = r, l
        bl, br = l // T, r // T

        if br - bl < 2:  # 中间没有完整块：整段当作散段直接统计
            vu = np.unique(a[l:r + 1])
            key = vu.astype(np.int64) * n1
            t = np.searchsorted(keys, key + r + 1) - np.searchsorted(keys, key + l)
            ans = int((((t & 1) == 0) & (t >= 2)).sum())
        else:
            # 两侧散段的互异值：先在完整块答案上做补偿
            idx = np.concatenate((np.arange(l, (bl + 1) * T), np.arange(br * T, r + 1)))
            vu = np.unique(a[idx])
            key = vu.astype(np.int64) * n1
            tin = pre[br][vu] - pre[bl + 1][vu]              # 该值在中间完整块 bl+1..br-1 的次数
            cl = (np.searchsorted(keys, key + (bl + 1) * T)
                  - np.searchsorted(keys, key + l))          # 左散段次数
            cr = (np.searchsorted(keys, key + r + 1)
                  - np.searchsorted(keys, key + br * T))     # 右散段次数
            t = tin + cl + cr
            # 总次数为正偶数 → 加 1；只在中间块里算成过正偶数 → 撤回 1
            ans = (g[bl + 1][br - 1]
                   + int((((t & 1) == 0) & (t >= 2)).sum()
                         - (((tin & 1) == 0) & (tin >= 2)).sum()))
        out.append(str(ans))

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

复杂度

设块数 $k = n/T$ （ $T = 1000$ ， $k \approx 100$ ）：

预处理 $g$ ： $O(k \cdot n)$ 次值级操作（numpy 向量化），空间 $O(k \cdot c)$ 的前缀和表 + $O(k^2)$ 的 $g$ 表；
单次询问：散段互异值 $\leqslant 2T$ ，去重与成对二分共 $O(T \log n)$ ，总计 $O(m \cdot \sqrt{n} \log n)$ 级。

整体与 C++ 正解同阶（ $O\!\left((n+m)\sqrt{n}\right)$ 量级），Python 只是常数更大；本题 OJ 限时 1 s，按 oj-python-style 约定接受 Python 超时，不换暴力。

总结

强制在线 + $n, m \leqslant 10^5$ 封死离线做法，指向"预处理全局信息 + 询问少量补偿"的分块结构。
区间拆成 中间完整块 + 两侧散段：完整块答案查表 $g[i][j]$ （ $O(1)$ ），散段值（ $\leqslant 2\sqrt n$ 个互异值）逐值二次补偿。
状态函数 $f(x) = [x \text{ 为正偶数}]$ 只看奇偶与是否非零，预处理扫描线和补偿公式因此都能增量维护。
Python 实现要点：把 (值, 位置) 编成排序键，任意值集合在任意位置区间的出现次数用一次成对 searchsorted 整组求出，避免逐值二分。
调试经验：解密公式的取模基数、"完整块右端是 $br-1$ 不是 $br$ "这两处错误在极小的样例上都不会暴露，必须用大数据验证。

图示解析

样例的分块拆解与补偿计算

以样例 $A = [1, 2, 2, 3, 1]$ 为例（为便于展示，示意块长取 $T = 2$ ，实际实现取 1000）：

块	$b_1$	$b_2$	$b_3$
位置（1 下标）	1, 2	3, 4	5
值	1, 2	2, 3	1

取询问 $[2, 5]$ ，转 0 下标后是 $[1, 4]$ ，于是 $bl = 0$ ， $br = 2$ ，三段拆解为：

text

1
2
3
4位置:   1  2 | 3  4 | 5
值:     1  2 | 2  3 | 1
          ~~   -----   ~~
[2,5] = 左散段{位置2: 值2} + 完整块 b2{值2, 值3} + 右散段{位置5: 值1}

拆解的观察重点：完整块是 $bl+1$ 到 $br-1$ ，只有 $b_2$ 一个块；块 $b_1$ 、 $b_3$ 各被切开一部分，它们贡献的元素全部以"散段"身份进入补偿环节。

第一步先查表： $g[1][1]$ 统计完整块 $b_2 = \{2, 3\}$ 内部的正偶数值——值 2 出现 1 次、值 3 出现 1 次，都不是正偶数，所以 $g[1][1] = 0$ 。

第二步对两侧散段的互异值并集 $vu = \{2, 1\}$ 逐值补偿（下表中次数均为 1 下标区间 $[2,5]$ 内的次数）：

值 $v$	$tin$ ：块 $b_2$ 中次数	散段次数	总次数 $t$	$f(t)$	$f(tin)$	修正量 $f(t)-f(tin)$
2	1（位置 3）	1（位置 2）	2	1	0	$+1$
1	0	1（位置 5）	1	0	0	$0$

答案 $= g[1][1] + (+1) + 0 = 0 + 1 = 1$ ，与直接数（值 2 在 $[2,5]$ 中出现位置 2、3 共 2 次）一致。

这张表恰好演示了补偿公式的三种典型情形，值得逐行对照：

值 2 是"修正量非零"的情形：它在完整块内只出现 1 次（ $f(tin) = f(1) = 0$ ， $g$ 没算它），加上散段后总次数变成 2，补偿 $+1$ 把它捡回来；
值 1 是"散段独有"的情形： $tin = 0$ ， $f(0) = 0$ ，补偿只按全区间次数 $f(1) = 0$ 计，不产生贡献；
若某值在完整块内出现 2 次、加散段后变 3 次（比如把询问改成 $[3, 5]$ 时值 2 不受影响，但可以想象 $b_2$ 内有两份值 2 的情形），则 $f(t) = 0$ 、 $f(tin) = 1$ ，修正量为 $-1$ ——补偿会撤掉 $g$ 中那份贡献。这正是"补偿是替换不是叠加"：每个散段互异值的贡献都被从状态 $f(tin)$ 替换成真实状态 $f(t)$ 。

对照 main.py 的查询分支：tin = pre[br][vu] - pre[bl+1][vu]（前缀和差，右端取 $br$ 不是 $br+1$ ），cl、cr 用 (值, 位置) 排序键成对二分算两侧散段次数，最后 g[bl+1][br-1] + Σf(t) − Σf(tin) 与本表逐项对应。

作诗

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

样例的分块拆解与补偿计算