琴 - 题目列表

形式化题目

给定长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$ ，每个数满足 $1 \leqslant a_i \leqslant 50$ 。有 $m$ 次询问，每次给出区间 $[l, r]$ ：把区间内的数从小到大排序后得到序列 $b$ ，从 $b_1$ 开始逐个访问，要求相邻两项满足 $b_{i+1} = b_i$ 或 $b_{i+1} = b_i + 1$ ，第一次不满足时停止。求每个询问实际访问的元素个数。

思路

一句话本质：值域只有 $1 \sim 50$ ，“排序后相邻差 $\leqslant 1$ "等价于"从区间内最小难度开始，难度值连续出现不断档”，答案就是 $\sum_{v=mn}^{first\_gap} cnt(v)$ ，其中 $mn$ 是区间内出现的最小难度， $first\_gap$ 是第一个出现次数为 $0$ 的难度值。

先看一个直接模拟题意的朴素解：

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/**
 * 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-08-28 23:40
 * update_at: 2026-08-28 23:40
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法：对每次询问，把区间内的曲目原样取出来、按难度从小到大排序，
//       再按题目规则逐首检查（下一首难度 = 上一首 或 上一首 + 1），不满足就终止。
//       这是对题面最直接的模拟，复杂度高，只适合小数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, m;
int a[MAXN];

// 直接模拟区间 [l, r] 的练习过程，返回练习的曲目数量。
int brute_ask(int l, int r) {
    vector<int> b;
    for (int i = l; i <= r; i++) {
        b.push_back(a[i]);
    }
    // 按难度从小到大排序
    sort(b.begin(), b.end());

    int ans = 1; // 区间内至少有一首，第一首一定被练习
    for (size_t i = 1; i < b.size(); i++) {
        // 下一首难度必须等于上一首，或比上一首大 1
        if (b[i] == b[i - 1] || b[i] == b[i - 1] + 1) {
            ans++;
        } else {
            break; // 出现断档，终止练习
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << brute_ask(l, r) << '\n';
    }

    return 0;
}

问题？ 区间内曲子按难度排序后，什么样的序列会让练习终止？

排序后序列非降，所以"相邻差 $\leqslant 1$ "就是"下一首难度等于上一首或比上一首大 $1$ "。这意味着难度只能原地重复或往上走 $1$ ，不能跳过任何一个整数难度值——从最小难度起，难度值必须连续地出现，出现断档就终止。

问题？ 同一难度的多首曲子，彼此之间的顺序会影响答案吗？

不会。排序后同一难度的曲子全部相邻，相邻差为 $0$ 永远合法，所以只要练到某个难度值，就会把它在区间里的全部曲子一次练完。答案只取决于"每个难度值在区间里出现几次"，与区间内曲子的原始排列完全无关。

问题？ "从最小难度开始连续练"如何变成一个可计算的式子？

设 $mn$ 是区间内出现的最小难度值。从 $mn$ 开始，只要难度 $v$ 出现过（ $cnt(v) > 0$ ），就可以练完它的全部曲子再进入 $v+1$ ；设 $first\_gap$ 是第一个满足 $cnt(v) = 0$ 的难度值，练完 $first\_gap-1$ 后，下一首难度至少是 $first\_gap+1$ （或没有曲目），差 $\geqslant 2$ ，练习立即终止。所以：

答案 = \sum_{v=mn}^{first\_gap-1} cnt(v)

问题？ 如何快速得到"难度 $v$ 在区间 $[l,r]$ 里出现几次"？

值域只有 $V=50$ ，对每个难度值 $v$ 各开一个前缀和数组： $pre[v][i]$ 表示前 $i$ 个位置中难度恰好为 $v$ 的数量。区间出现次数就是 $pre[v][r] - pre[v][l-1]$ ，一次 $O(1)$ 查询。

这张"难度桶"图用样例 2 的数据演示区间 $[1,4] = \{2,3,5,6\}$ 的断档过程：

text

1
2
3
4
5难度值:    1  2  3  4  5  6
出现次数:  0  1  1  0  1  1
             ↑mn ↑    ↑
              └─累加─┘  第一个断档(出现 0 次)，在此停止
答案 = cnt(2) + cnt(3) = 1 + 1 = 2

观察上图：从最小出现难度 $mn=2$ 开始逐个累加，难度 $4$ 出现 $0$ 次是第一个断档，练习在练完难度 $3$ 后终止；难度 $5,6$ 虽然存在，但因为断档已经无法练到。

问题？ 怎么定位 $mn$ 和第一个断档？

每个询问从 $1$ 到 $50$ 扫一遍：第一个出现次数 $>0$ 的难度就是 $mn$ ；再从 $mn$ 开始累加出现次数，遇到第一个出现次数为 $0$ 的难度就停止。每次询问 $O(50)$ ，预处理 $O(n \times 50)$ 。

代码

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/**
 * 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-08-28 23:40
 * update_at: 2026-08-28 23:40
 */
// main.cpp：T3 琴(instrument) 最终解。
// 值域只有 1..50，对每个难度值 v 开一个前缀和数组，
// 每次询问从区间内出现的最小难度 mn 开始累加出现次数，遇到断档(次数为 0)就停止。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXV = 50;

int n, m;
int a[MAXN];
// pre[v][i]：前 i 个位置中难度值恰好为 v 的曲目数量
int pre[MAXV + 1][MAXN + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 预处理：每个难度值一个前缀和数组，O(n * V)
    for (int v = 1; v <= MAXV; v++) {
        for (int i = 1; i <= n; i++) {
            pre[v][i] = pre[v][i - 1] + (a[i] == v);
        }
    }

    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;

        // 第一步：找区间内出现的最小难度 mn
        int mn = 0;
        for (int v = 1; v <= MAXV; v++) {
            if (pre[v][r] - pre[v][l - 1] > 0) {
                mn = v;
                break;
            }
        }

        // 第二步：从 mn 开始累加各难度出现次数，遇到第一个断档(出现次数为 0)就停
        int total = 0;
        for (int v = mn; v <= MAXV; v++) {
            int cnt = pre[v][r] - pre[v][l - 1];
            if (cnt == 0) break;
            total += cnt;
        }
        cout << total << '\n';
    }

    return 0;
}

复杂度

预处理： $O(nV)$ ， $V = 50$ 。
每次询问： $O(V)$ 。
总复杂度： $O((n+m)V)$ ，约 $10^7$ 次操作。
空间： $O(nV)$ ，pre[51][100001] 约 20MB，远小于 512MB 限制。

总结

本题的钥匙是"小值域"： $a_i \leqslant 50$ 意味着把逐首检查换成"按难度值检查"。练习规则在排序后坍缩成"从最小值起连续不断档"，于是答案变成一段难度值出现次数之和，用每个值一个前缀和数组即可 $O(1)$ 取出现次数。这类"值域极小 → 桶/前缀和"的思路（二维前缀和的退化形态）在值域类题目中非常常见，值得记下。

图示解析

这张图展示从题面到算法的完整推理路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16区间内曲目按难度排序
        │
        ▼
排序后非降，相邻差<=1 ⇔ 难度只能 相等 或 +1
        │
        ▼
同一难度必然整批练完，答案只取决于每个难度值的出现次数
        │
        ▼
从最小出现难度 mn 起连续累加，第一个 cnt(v)==0（断档）即停止
        │
        ▼
cnt(v) 用每个值一个前缀和数组 O(1) 查询  ← 值域只有 50
        │
        ▼
每次询问 O(50)，总 O((n+m)·50)

从图的上到下看：排序把"排列"问题变成"值域"问题，断档把"逐首模拟"变成"区间和"，小值域最终把每次询问压到常数 50。整条路线的每一步都是等价变形，没有丢失信息。

琴

目录

形式化题目

思路

代码

复杂度

总结

图示解析