深度优先搜索与广度优先搜索

深度优先搜索；广度优先搜索。

概念

DFS 沿一条路径尽量走深，走不通再回溯；BFS 按层次扩展，用队列保证先到达的距离最短（边权为 1 时）。二者是通用搜索框架，可作用在树、图、网格或抽象状态图上。本叶子强调搜索过程、队列/栈/递归栈、visited 标记与复杂度，与 cspj.algo.graph-traversal 区分：后者侧重「图上的遍历语义 + Flood Fill 连通块」，更贴近网格/邻接表题面；与 cspj.cpp.recursion 区分：DFS 常写递归，但这里考的是搜索策略而非函数语法。复赛 210 分钟里，BFS 常出现在带时间/层数约束的最短路或可达性判定。

CSP-J 常考

cspj-r1-2020 第 30–33 题：阅读程序，DFS/BFS 遍历树或图，问访问顺序或节点状态。
cspj-r1-2021 第 14 题：单选题，DFS 与 BFS 性质或适用场景。
cspj-r2-2019 第 4 题：复赛编程，无向图 BFS 预处理距离，判断影响范围。
cspj-r2-2023 第 4 题：复赛编程，带开放时间约束，在 (节点, 时间 mod k) 状态图上 BFS。
cspj-r2-2024 第 4 题：复赛编程，多轮接龙约束下的可达性，状态 BFS。

// 网格 BFS：四方向，求 (sr,sy) 到 (tr,ty) 的最短步数
queue<pair<int,int>> q;
q.push({sr, sy});
vis[sr][sy] = true;
while (!q.empty()) {
    auto [x,y] = q.front(); q.pop();
    for (auto [dx,dy] : {{1,0},{-1,0},{0,1},{0,-1}}) {
        int nx = x+dx, ny = y+dy;
        if (in(nx,ny) && !vis[nx][ny]) {
            vis[nx][ny] = true;
            q.push({nx,ny});
        }
    }
}

易错点

DFS 递归忘记回溯标记（若需要找所有路径），或 BFS 忘记入队时立刻标记导致重复入队。
阅读程序里栈/队列操作顺序与「先访问谁」搞混，手 trace 时要写出队头或递归返回点。
抽象状态 BFS 状态维数漏了（如时间 mod k），导致判可达错误。

编程题

加工零件

C++时间 1 s内存 256 MB 文件 IO：work.in → work.out

凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 $n$ 位工人，工人们从 $1 \sim n$ 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。

如果 $x$ 号工人想生产一个被加工到第 $L\,(L \gt 1)$ 阶段的零件，则所有与 $x$ 号工人有传送带直接相连的工人，都需要生产一个被加工到第 $L - 1$ 阶段的零件（但 $x$ 号工人自己无需生产第 $L - 1$ 阶段的零件）。

如果 $x$ 号工人想生产一个被加工到第 $1$ 阶段的零件，则所有与 $x$ 号工人有传送带直接相连的工人，都需要为 $x$ 号工人提供一个原材料。

轩轩是 $1$ 号工人。现在给出 $q$ 张工单，第 $i$ 张工单表示编号为 $a_i$ 的工人想生产一个第 $L_i$ 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！

输入格式

第一行三个正整数 $n$ ， $m$ 和 $q$ ，分别表示工人的数目、传送带的数目和工单的数目。

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$ ，表示编号为 $u$ 和 $v$ 的工人之间存在一条零件传输带。保证 $u \neq v$ 。

接下来 $q$ 行，每行两个正整数 $a$ 和 $L$ ，表示编号为 $a$ 的工人想生产一个第 $L$ 阶段的零件。

输出格式

共 $q$ 行，每行一个字符串 Yes 或者 No。如果按照第 $i$ 张工单生产，需要编号为 1 的轩轩提供原材料，则在第 $i$ 行输出 Yes；否则在第 $i$ 行输出 No。

样例

输入 1

输出 1

No
Yes
No
Yes
No
Yes

编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。

编号为 2 的工人想生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

编号为 3 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

编号为 2 的工人想生产第 2 阶段的零件，需要编号为 1 和 3 的工人生产第 1 阶段的零件，他/她们都需要编号为 2 的工人提供原材料。

编号为 3 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

输入 2

输出 2

No
Yes
No
Yes
Yes

编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 和 5 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 和 5 的工人生产第 1 阶段的零件，需要编号为 1,3,4 的工人提供原材料。

编号为 1 的工人想生产第 3 阶段的零件，需要编号为 2 和 5 的工人生产第 2 阶段的零件，需要编号为 1,3,4 的工人生产第 1 阶段的零件，需要编号为 2,3,4,5 的工人提供原材料。

编号为 1 的工人想生产第 4 阶段的零件，需要编号为 2 和 5 的工人生产第 3 阶段的零件，需要编号为 1,3,4 的工人生产第 2 阶段的零件，需要编号为 2,3,4,5 的工人生产第 1 阶段的零件，需要全部工人提供原材料。

编号为 1 的工人想生产第 5 阶段的零件，需要编号为 2 和 5 的工人生产第 4 阶段的零件，需要编号为 1,3,4 的工人生产第 3 阶段的零件，需要编号为 2,3,4,5 的工人生产第 2 阶段的零件，需要全部工人生产第 1 阶段的零件，需要全部工人提供原材料。

数据范围

共 $20$ 个测试点。

对所有测试点保证 $1 \leq u, v, a \leq n$ 。

测试点 $1\sim4$ ， $1 \leq n, m \leq 1000$ ， $q = 3$ ， $L = 1$ 。

测试点 $5\sim8$ ， $1 \leq n, m \leq 1000$ ， $q = 3$ ， $1 \leq L \leq 10$ 。

测试点 $9\sim12$ ， $1 \leq n, m, L \leq 1000$ ， $1 \leq q \leq 100$ 。

测试点 $13\sim16$ ， $1 \leq n, m, L \leq 1000$ ， $1 \leq q \leq 10^5$ 。

测试点 $17\sim20$ ， $1 \leq n, m, q \leq 10^5$ ， $1 \leq L \leq 10^9$ 。

部分分

20 分
测试点 $1\sim4$ ： $1 \leq n, m \leq 1000$ ， $q = 3$ ， $L = 1$ 。
20 分
测试点 $5\sim8$ ： $1 \leq n, m \leq 1000$ ， $q = 3$ ， $1 \leq L \leq 10$ 。
20 分
测试点 $9\sim12$ ： $1 \leq n, m, L \leq 1000$ ， $1 \leq q \leq 100$ 。
20 分
测试点 $13\sim16$ ： $1 \leq n, m, L \leq 1000$ ， $1 \leq q \leq 10^5$ 。
20 分
测试点 $17\sim20$ ： $1 \leq n, m, q \leq 10^5$ ， $1 \leq L \leq 10^9$ 。

原文保真说明：原卷印刷错误 1 处（照原卷保留，未作修改）

原卷印刷如此其它name
原卷作 加工零件
原卷第 8 页题目标题印作「加工零件」；第 1 页题目概况表中文名称印作「零件加工」。本题 name 按题面页标题录入。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

#include <algorithm>#include <iostream>using namespace std;int n;int d[50][2];int ans;void dfs(int n, int sum) { if (n == 1) { ans = max(sum, ans); return; } for (int i = 1; i < n; ++i) { int a = d[i - 1][0], b = d[i - 1][1]; int x = d[i][0], y = d[i][1]; d[i - 1][0] = a + x; d[i - 1][1] = b + y; for (int j = i; j < n - 1; ++j) d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1]; int s = a + x + abs(b - y); dfs(n - 1, sum + s); for (int j = n - 1; j > i; --j) d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1]; d[i - 1][0] = a, d[i - 1][1] = b; d[i][0] = x, d[i][1] = y; }}int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> d[i][0]; for (int i = 0; i < n; ++i) cin >> d[i][1]; ans = 0; dfs(n, 0); cout << ans << endl; return 0;}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序
原卷作 for (int i = 0; i < n; ++i) cin >> d[i][0]; ，常规写法应为 for (int i = 0; i < n; ++i) cin >> d[i][0];
洛谷抓取件 program.code 含行尾填充空格且 main 读入 d[i][1] 循环格式不同；pages/pg-06.png–pg-07.png 逐行核对后已恢复。
已按官方原件恢复：现为原卷原文

30判断1.5 分
输出的数一定不小于输入的 d[i][0] 和 d[i][1] 的任意一个。（）

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序
原卷作 for (int i = 0; i < n; ++i) cin >> d[i][0]; ，常规写法应为 for (int i = 0; i < n; ++i) cin >> d[i][0];
洛谷抓取件 program.code 含行尾填充空格且 main 读入 d[i][1] 循环格式不同；pages/pg-06.png–pg-07.png 逐行核对后已恢复。
已按官方原件恢复：现为原卷原文

31单选3 分
- 单选题
  1. 若输入的 $n$ 为 $20$ ，接下来的输入是 $20$ 个 $9$ 和 $20$ 个 $0$ ，则输出为（）。
A
1890

B
1881

C
1908

D
1917

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序
原卷作 for (int i = 0; i < n; ++i) cin >> d[i][0]; ，常规写法应为 for (int i = 0; i < n; ++i) cin >> d[i][0];
洛谷抓取件 program.code 含行尾填充空格且 main 读入 d[i][1] 循环格式不同；pages/pg-06.png–pg-07.png 逐行核对后已恢复。
已按官方原件恢复：现为原卷原文

32单选3 分
若输入的 $n$ 为 $30$ ，接下来的输入是 $30$ 个 $0$ 和 $30$ 个 $5$ ，则输出为（）。

A
2000

B
2010

C
2030

D
2020

阅读程序共 4 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序
原卷作 for (int i = 0; i < n; ++i) cin >> d[i][0]; ，常规写法应为 for (int i = 0; i < n; ++i) cin >> d[i][0];
洛谷抓取件 program.code 含行尾填充空格且 main 读入 d[i][1] 循环格式不同；pages/pg-06.png–pg-07.png 逐行核对后已恢复。
已按官方原件恢复：现为原卷原文

33单选4 分
（4 分）若输入的 $n$ 为 $15$ ，接下来的输入是 $15$ 到 $1$ ，以及 $15$ 到 $1$ ，则输出为（）。

A
2440

B
2220

C
2240

D
2420

以 $a$ 为起点，对下边的无向图进行深度优先遍历，则 $b,c,d,e$ 四个点中有可能作为最后一个遍历到的点的个数为（）。

编程题

旅游巴士

C++时间 1 s内存 512 MB 文件 IO：bus.in → bus.out

小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有 $n$ 处地点，在这些地点之间连有 $m$ 条道路。其中 $1$ 号地点为景区入口， $n$ 号地点为景区出口。我们把一天当中景区开门营业的时间记为 $0$ 时刻，则从 $0$ 时刻起，每间隔 $k$ 单位时间便有一辆旅游巴士到达景区入口，同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能单向通行。对于每条道路，游客步行通过的用时均为恰好 $1$ 单位时间。

小 Z 希望乘坐旅游巴士到达景区入口，并沿着自己选择的任意路径走到景区出口，再乘坐旅游巴士离开，这意味着他到达和离开景区的时间都必须是 $k$ 的非负整数倍。由于节假日客流众多，小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动，而不想在任何地点（包括景区入口和出口）或者道路上停留。

出发前，小 Z 忽然得知：景区采取了限制客流的方法，对于每条道路均设置了一个
“开放时间” $a _ i$ ，游客只有不早于 $a _ i$ 时刻才能通过这条道路。

请帮助小 Z 设计一个旅游方案，使得他乘坐旅游巴士离开景区的时间尽量地早。

输入格式

从文件 bus.in 中读入数据。

输入的第一行包含 $3$ 个正整数 $n, m, k$ ，表示旅游景点的地点数、道路数，以及旅游巴士的发车间隔。

输入的接下来 $m$ 行，每行包含 $3$ 个非负整数 $u _ i, v _ i, a_ i$ ，表示第 $i$ 条道路从地点 $u _ i$ 出发，到达地点 $v _ i$ ，道路的“开放时间”为 $a _ i$ 。

输出格式

输出到文件 bus.out 中。

输出一行，仅包含一个整数，表示小 Z 最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案，输出 -1。

样例

输入 1

输出 1

小 Z 可以在 $3$ 时刻到达景区入口，沿 $1 \to 3 \to 4 \to 5$ 的顺序走到景区出口，并在 $6$ 时刻离开。

数据范围

对于所有测试数据有： $2 \le n \le 10^4$ ， $1 \le m \le 2 \times 10^4$ ， $1 \le k \le 100$ ， $1 \le u_i, v_i \le n$ ， $0 \le a_i \le 10^6$ 。

测试点编号	$n \le$	$m \le$	$k \le$	特殊性质
$1 \sim 2$	$10$	$15$	$100$	$a_i = 0$
$3 \sim 5$	$10$	$15$	$100$	无
$6 \sim 7$	$10^4$	$2 \times 10^4$	$1$	$a_i = 0$
$8 \sim 10$	$10^4$	$2 \times 10^4$	$1$	无
$11 \sim 13$	$10^4$	$2 \times 10^4$	$100$	$a_i = 0$
$14 \sim 15$	$10^4$	$2 \times 10^4$	$100$	$u_i < v_i$
$16 \sim 20$	$10^4$	$2 \times 10^4$	$100$	无

部分分

10 分
测试点 $1 \sim 2$ ： $n \le 10$ ， $m \le 15$ ， $k \le 100$ ， $a_i = 0$ 。
15 分
测试点 $3 \sim 5$ ： $n \le 10$ ， $m \le 15$ ， $k \le 100$ ，无特殊性质。
10 分
测试点 $6 \sim 7$ ： $n \le 10^4$ ， $m \le 2 \times 10^4$ ， $k \le 1$ ， $a_i = 0$ 。
15 分
测试点 $8 \sim 10$ ： $n \le 10^4$ ， $m \le 2 \times 10^4$ ， $k \le 1$ ，无特殊性质。
15 分
测试点 $11 \sim 13$ ： $n \le 10^4$ ， $m \le 2 \times 10^4$ ， $k \le 100$ ， $a_i = 0$ 。
10 分
测试点 $14 \sim 15$ ： $n \le 10^4$ ， $m \le 2 \times 10^4$ ， $k \le 100$ ， $u_i < v_i$ 。
25 分
测试点 $16 \sim 20$ ： $n \le 10^4$ ， $m \le 2 \times 10^4$ ， $k \le 100$ ，无特殊性质。

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它数据范围
原卷作 | $14 \sim 15$ | $10^4$ | $2 \times 10^4$ | $100$ | $u_i < v_i$ |
洛谷 P9751 测试点表第 14–15 档特殊性质写 $u_i \le v_i$；官方 PDF 第 11 页图像为准：$u_i < v_i$（严格小于）。
已按官方原件恢复：现为原卷原文

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

编程题

接龙

C++时间 2 s内存 512 MB 文件 IO：chain.in → chain.out

在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。

总共有 $n$ 个人参与这个接龙游戏，第 $i$ 个人会获得一个整数序列 $S_i$ 作为他的词库。

一次游戏分为若干轮，每一轮规则如下：

$n$ 个人中的某个人 $p$ 带着他的词库 $S_p$ 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
接龙的人选择一个长度在 $[2, k]$ $[2, k]$ 的 $S_p$ $S_{p}$ 的连续子序列 $A$ $A$ 作为这一轮的接龙序列，其中 $k$ $k$ 是给定的常数。若这是游戏的第一轮，那么 $A$ $A$ 需要以元素 $1$ $1$ 开头，否则 $A$ $A$ 需要以上一轮的接龙序列的最后一个元素开头。
- 序列 $A$ 是序列 $S$ 的连续子序列当且仅当可以通过删除 $S$ 的开头和结尾的若干元素（可以不删除）得到 $A$ 。

为了强调合作，小 J 给了 $n$ 个参与游戏的人 $q$ 个任务，第 $j$ 个任务需要这 $n$ 个人进行一次游戏，在这次游戏里进行恰好 $r_j$ 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 $c_j$ 。为了保证任务的可行性，小 J 请来你判断这 $q$ 个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。

输入格式

从文件 chain.in 中读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n, k, q$ ，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。

接下来 $n$ 行：

第 $i$ 行包含 $(l_i + 1)$ 个整数 $l_i, S_{i,1}, S_{i,2}, \dots , S_{i,l_i}$ ，其中第一个整数 $l_i$ 表示序列 $S_i$ 的长度，接下来 $l_i$ 个整数描述序列 $S_i$ 。

接下来 $q$ 行：

第 $j$ 行包含两个整数 $r_j, c_j$ ，描述一个任务。

输出格式

输出到文件 chain.out 中。

对于每个任务：输出一行包含一个整数，若任务可以完成输出 1，否则输出 0。

样例

输入 1

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

输出 1

在下文中，我们使用 $\{A_i\} = \{A_1, A_2, \ldots, A_r\}$ 表示一轮游戏中所有的接龙序列， $\{p_i\} = \{p_1, p_2, \ldots, p_r\}$ 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。

对于第一组询问， $p_1 = 1$ 、 $A_1 = 12$ 是一个满足条件的游戏过程。
对于第二组询问，可以证明任务不可完成。注意 $p_1 = 1$ 、 $A_1 = 1234$ 不是合法的游戏过程，因为此时 $|A_1| = 4 > k$ 。
对于第三组询问， $\{p_i\} = \{2, 1\}$ 、 $\{A_i\} = \{12, 234\}$ 是一个满足条件的游戏过程。
对于第四组询问，可以证明任务不可完成。注意 $\{p_i\} = \{2, 1, 1\}$ 、 $\{A_i\} = \{12, 23, 34\}$ 不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 $k$ ，但第二轮和第三轮由同一个人接龙，不符合要求。
对于第五组询问， $\{p_i\} = \{1, 2, 3, 1, 2, 3\}$ 、 $\{A_i\} = \{12, 25, 51, 12, 25, 516\}$ 是一个满足条件的游戏过程。
对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 $2$ ，因此 $A_1 = 1$ 不是一个合法的游戏过程。
对于第七组询问，所有人的词库均不存在字符 $\tt 7$ ，因此任务显然不可完成。

数据范围

对于所有测试数据，保证：

$1 \le T \le 5$ ；
$1 \le n \le 10^5$ ， $2 \le k \le 2 \times 10^5$ ， $1 \le q \le 10^5$ ；
$1 \le l_i \le 2 \times 10^5$ ， $1 \le S_{i,j} \le 2 \times 10^5$ ；
$1 \le r_j \le 10^2$ ， $1 \le c_j \le 2 \times 10^5$ ；
设 $\sum l$ 为单组测试数据内所有 $l_i$ 的和，则 $\sum l \le 2 \times 10^5$ 。

测试点	$n \le$	$r \le$	$\sum l \le$	$q \le$	特殊性质
$1$	$10^3$	$1$	$2000$	$10^3$	无
$2, 3$	$10$	$5$	$20$	$10^2$	无
$4, 5$	$10^3$	$10$	$2000$	$10^3$	A
$6$	$10^5$	$10^2$	$2 \times 10^5$	$10^5$	A
$7, 8$	$10^3$	$10$	$2000$	$10^3$	B
$9, 10$	$10^5$	$10^2$	$2 \times 10^5$	$10^5$	B
$11, 12$	$10^3$	$10$	$2000$	$10^3$	C
$13, 14$	$10^5$	$10^2$	$2 \times 10^5$	$10^5$	C
$15 \sim 17$	$10^3$	$10$	$2000$	$10^3$	无
$18 \sim 20$	$10^5$	$10^2$	$2 \times 10^5$	$10^5$	无

特殊性质 A：保证 $k = 2 \times 10^5$ 。

特殊性质 B：保证 $k \le 5$ 。

特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 $5$ 。

部分分

5 分
测试点 $1$ ： $n \le 10^3$ ， $r \le 1$ ， $\sum l \le 2000$ ， $q \le 10^3$ ，无特殊性质。
10 分
测试点 $2, 3$ ： $n \le 10$ ， $r \le 5$ ， $\sum l \le 20$ ， $q \le 10^2$ ，无特殊性质。
10 分
测试点 $4, 5$ ： $n \le 10^3$ ， $r \le 10$ ， $\sum l \le 2000$ ， $q \le 10^3$ ，特殊性质 A。
5 分
测试点 $6$ ： $n \le 10^5$ ， $r \le 10^2$ ， $\sum l \le 2 \times 10^5$ ， $q \le 10^5$ ，特殊性质 A。
10 分
测试点 $7, 8$ ： $n \le 10^3$ ， $r \le 10$ ， $\sum l \le 2000$ ， $q \le 10^3$ ，特殊性质 B。
10 分
测试点 $9, 10$ ： $n \le 10^5$ ， $r \le 10^2$ ， $\sum l \le 2 \times 10^5$ ， $q \le 10^5$ ，特殊性质 B。
10 分
测试点 $11, 12$ ： $n \le 10^3$ ， $r \le 10$ ， $\sum l \le 2000$ ， $q \le 10^3$ ，特殊性质 C。
10 分
测试点 $13, 14$ ： $n \le 10^5$ ， $r \le 10^2$ ， $\sum l \le 2 \times 10^5$ ， $q \le 10^5$ ，特殊性质 C。
15 分
测试点 $15 \sim 17$ ： $n \le 10^3$ ， $r \le 10$ ， $\sum l \le 2000$ ， $q \le 10^3$ ，无特殊性质。
15 分
测试点 $18 \sim 20$ ： $n \le 10^5$ ， $r \le 10^2$ ， $\sum l \le 2 \times 10^5$ ， $q \le 10^5$ ，无特殊性质。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB