[CSP-J 2024] 接龙

GitHub跳转原题关系图返回列表

沿着 5、15、60、100 分的数据范围逐层优化：先枚举有色边，再压缩接龙人状态，最后用扫描窗口消除平方级边数。

OJ: luogu

题目 ID: P11230

难度:提高

标签:建模动态规划状态压缩滑动窗口枚举

创建: 2026-07-05 21:24

更新: 2026-10-07 10:45

形式化题目

第 $p$ 个人持有序列 $S_p$ 。一次操作可以在 $S_p$ 中选择两个位置 $i<j$ ，满足

2\leqslant j-i+1\leqslant k,

并完成一次从 $S_{p,i}$ 到 $S_{p,j}$ 的转移。连续两次转移不能选择同一个人。

初始值为 $1$ 。每个询问给出 $(r,c)$ ，要求判断能否恰好转移 $r$ 次后到达 $c$ 。

把每个合法选择看成一条边：

text

1S[p][i] -> S[p][j]，边的颜色为 p

于是问题等价为：能否从 $1$ 出发走恰好 $r$ 条边到达 $c$ ，并且相邻两条边颜色不同。

解法路线

设 $L=\sum l_i$ ， $R=\max r_j$ ，值域大小为 $V=2\times 10^5$ 。按每个测试点 $5$ 分计算，可以得到下面的拿分路线。

层次	利用的数据范围	做法	可覆盖测试点	累计分数
第一层	$r=1$	只枚举第一轮的合法连续子序列	$1$	$5$
第二层	$n\leqslant10,L\leqslant20,R\leqslant5$	保留第一层特判，其余询问记忆化搜索	$1\sim3$	$15$
第三层	$L\leqslant2000,R\leqslant10$	枚举全部有色边，按轮数做 DP	$1\sim5,7,8,11,12,15\sim17$	$60$
第四层	完整范围	两个接龙人压状态，扫描窗口压边	全部	$100$

每一层代码都保留前一层的能力，因此可以作为一份独立提交逐步拿分。测试点 $4\sim14$ 中的特殊性质 A、B、C 不是一条 A 到 B 再到 C 的递进链，而是三个并列提示：

A 中 $k$ 很大，合法结尾接近一个后缀，提示我们批量处理区间；
B 中 $k\leqslant5$ ，每个起点只有常数个结尾，逐一枚举边就不再平方爆炸；
C 中每个值至多出现 $5$ 次，按“相同值”寻找下一轮起点时只有常数个候选。

三条支线最后汇合到同一个正解：相同值之间负责连接相邻两轮，同一个人序列中的位置区间负责完成当前轮。

子任务解法： $r=1$

适用范围

测试点 $1$ 的所有询问都满足 $r=1$ ，只需判断哪些值能作为第一轮的结尾。

思路

第一轮没有“与上一轮同一个人”的限制，只要求接龙序列从值 $1$ 开始。因此对每个人的序列枚举所有值为 $1$ 的位置 left，再枚举

left+1\leqslant right\leqslant\min(l_p,left+k-1)

把 S[p][right] 标记为一轮可达。全部询问随后直接查表。

代码

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/**
 * 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-09-27 21:38
 * update_at: 2026-09-27 21:38
 */
// subtask_05.cpp：测试点 1，所有询问都只有一轮接龙。
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 200005;

bool reachable[MAXV];

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

    int T;
    cin >> T;
    while (T--) {
        int n, k, q;
        cin >> n >> k >> q;

        memset(reachable, 0, sizeof(reachable));

        for (int person = 1; person <= n; person++) {
            int len;
            cin >> len;
            vector<int> seq(len + 1);
            for (int i = 1; i <= len; i++) {
                cin >> seq[i];
            }

            // 第一轮必须从值 1 开始。
            for (int left = 1; left <= len; left++) {
                if (seq[left] != 1) continue;
                int right_end = min(len, left + k - 1);
                for (int right = left + 1; right <= right_end; right++) {
                    reachable[seq[right]] = true;
                }
            }
        }

        for (int i = 1; i <= q; i++) {
            int round, value;
            cin >> round >> value;
            // 本文件只面向保证 round = 1 的测试点。
            cout << (round == 1 && reachable[value] ? 1 : 0) << '\n';
        }
    }

    return 0;
}

复杂度与瓶颈

这一层仍会显式枚举所有第一轮有色边。设边数为 $E$ ，时间复杂度为 $O(E+q)$ ，空间复杂度为 $O(V)$ ；最坏 $E=O(L^2)$ ，但测试点 $1$ 的 $L\leqslant2000$ 。

当询问轮数增加后，只知道“某个值一轮可达”已经不够，还必须知道上一轮由谁接龙。

暴力解法： $L\leqslant20$

适用范围

测试点 $2,3$ 满足 $n\leqslant10$ 、 $L\leqslant20$ 、 $R\leqslant5$ 。规模足够小，可以现场逐一枚举所有合法连续子序列（有色边），边用完即丢，不必保存边表。

代码保留 r=1 的直接查表分支，因此同一份程序也能通过测试点 $1$ ，累计获得 $15$ 分。

思路

搜索状态写成三元组：

(round,value,lastPerson),

分别表示已经完成的轮数、当前结尾值、上一轮的接龙人。

要找从当前值出发的出边，扫描所有人的序列、枚举以当前值开头的合法接龙序列即可。从中枚举颜色不等于 lastPerson 的边。走过边 $(value,to,p)$ 后，进入状态

(round+1,to,p)

当 round == targetRound 时，检查 value == targetValue。相同状态的答案相同，因此可以记忆化。

代码

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-09-27 21:38
 * update_at: 2026-10-01 18:42
 */
// subtask_15.cpp：测试点 1 特判；测试点 2、3 逐询问记忆化搜索。
// 不保存边表：搜索到某个状态时，现场扫描所有人的序列，
// 枚举以当前值开头的合法接龙序列（有色边），用完即丢。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXV = 200005;   // 值的范围
const int MAXR = 10;       // 测试点 2、3 保证 r <= 5，留富余
const int MAXP = 12;       // 测试点 2、3 保证 n <= 10，留富余

// 一个询问：恰好 r 轮接龙后，最后一个元素是否恰好为 v
struct Query {
    ll r;
    ll v;
};

ll n, k, q;
ll max_value;
ll target_round, target_value;

vector<vector<ll> > seq;    // seq[person] = 第 person 个人的序列，下标从 1 开始用
vector<char> one_round;     // one_round[v] = 1 表示一轮就能以 v 结尾

// memo[round][value][person]：状态 (round, value, person) 的搜索结果
//   0 = 还没搜过，1 = 失败，2 = 成功
// person = 0 表示还没有真正的上一轮接龙人（第 0 轮）。
char memo[MAXR][MAXV][MAXP];

// 从 (round, value, last_person) 出发，判断能否恰好 target_round 轮后以 target_value 结尾。
bool dfs_game(ll round, ll value, ll last_person) {
    if (round == target_round) {
        return value == target_value;
    }

    // 同样的状态搜过一次就够了，直接复用上次的结论。
    if (memo[round][value][last_person] != 0) {
        return memo[round][value][last_person] == 2;
    }

    // 现场枚举所有以 value 开头、接龙人不是 last_person 的合法接龙序列。
    for (ll person = 1; person <= n; person++) {
        if (person == last_person) continue;

        vector<ll>& s = seq[person];
        ll len = s.size() - 1;
        for (ll left = 1; left <= len; left++) {
            if (s[left] != value) continue;

            // 接龙序列长度在 [2, k]，结尾 right ∈ [left + 1, left + k - 1]
            ll right_end = min(len, left + k - 1);
            for (ll right = left + 1; right <= right_end; right++) {
                if (dfs_game(round + 1, s[right], person)) {
                    memo[round][value][last_person] = 2;
                    return true;
                }
            }
        }
    }

    memo[round][value][last_person] = 1;
    return false;
}

// 测试点 1（r = 1）：枚举所有以 1 开头的合法接龙序列，标记一轮可达的结尾值。
void compute_one_round() {
    one_round.assign(max_value + 1, 0);

    for (ll person = 1; person <= n; person++) {
        vector<ll>& s = seq[person];
        ll len = s.size() - 1;
        for (ll left = 1; left <= len; left++) {
            if (s[left] != 1) continue;

            ll right_end = min(len, left + k - 1);
            for (ll right = left + 1; right <= right_end; right++) {
                one_round[s[right]] = 1;
            }
        }
    }
}

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

    ll T;
    cin >> T;
    while (T--) {
        cin >> n >> k >> q;

        seq.assign(n + 1, vector<ll>());
        max_value = 1;
        for (ll person = 1; person <= n; person++) {
            ll len;
            cin >> len;
            seq[person].resize(len + 1);
            for (ll i = 1; i <= len; i++) {
                cin >> seq[person][i];
                max_value = max(max_value, seq[person][i]);
            }
        }

        vector<Query> queries(q + 1);
        for (ll i = 1; i <= q; i++) {
            cin >> queries[i].r >> queries[i].v;
            max_value = max(max_value, queries[i].v);
        }

        compute_one_round();

        for (ll i = 1; i <= q; i++) {
            if (queries[i].r == 1) {
                cout << (one_round[queries[i].v] ? 1 : 0) << '\n';
                continue;
            }

            target_round = queries[i].r;
            target_value = queries[i].v;

            // 目标变了，把上一个询问留下的搜索结果清掉。
            for (ll r = 0; r < target_round; r++) {
                memset(memo[r], 0, sizeof(memo[r]));
            }

            cout << (dfs_game(0, 1, 0) ? 1 : 0) << '\n';
        }
    }

    return 0;
}

复杂度与瓶颈

设全部有色边的条数为

E=\sum_{p=1}^{n}\sum_{i=1}^{l_p}\min(k-1,l_p-i)

最坏情况下 $E=O(L^2)$ 。不保存边表后，每个搜索状态现场花 $O(L)$ 找出全部出边，转移代价为 $O(L+E_v)$ （ $E_v$ 为从 $v$ 出发的边数），对 $L\leqslant20$ 的规模没有影响。记忆化虽然避免了重复搜索状态，但每个询问仍要单独搜索；当 $q$ 、 $L$ 或 $R$ 增大时都会失效。

下一层先解决“每个询问重复搜索”的问题。

子任务解法： $L\leqslant2000,R\leqslant10$

适用范围

所有满足 $L\leqslant2000$ 、 $R\leqslant10$ 的测试点都没有必要分别利用 A、B、C。直接按最坏 $O(L^2)$ 双重循环逐一枚举有色边，也只有约 $2\times10^6$ 条边要检查，不必把它们保存下来。

因此这一做法能统一覆盖测试点

1\sim5,\quad 7,8,\quad 11,12,\quad 15\sim17

共 $12$ 个测试点，即 $60$ 分。

思路

先读完所有询问，求出最大轮数 $R$ ，再统一预处理第 $1$ 到第 $R$ 轮的可达状态。这样每个询问只需查表，不再重复搜索。

若朴素保存状态 reachable[value][person]，会多出很大的一维。注意下一轮选择人 $p$ 时，我们只问一件事：

到达当前值的方案中，是否存在一个上一轮接龙人不等于 $p$ ？

因此，每个值只需保留最多两个不同的接龙人：

没有代表人：这个值不可达；
只有代表人 $x$ ：下一轮不能选 $x$ ，其他人都能选；
有两个不同代表人 $x,y$ ：无论下一轮选择谁， $x,y$ 中至少有一个人与他不同。

第 $0$ 轮令值 $1$ 的代表人为特殊编号 $0$ ，表示还没有真正选择接龙人。

每一轮按人扫描他的序列，用双重循环现场枚举这个人的全部有色边，边用完即丢，不保存边表。如果边为 $(u,v,p)$ ，且 $u$ 的两个代表人中存在一个不等于 $p$ ，就把 $p$ 加入 $v$ 的下一轮代表人集合。

代码

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
140
141
142
143
144
145
146
147
148/**
 * 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-09-27 21:29
 * update_at: 2026-10-01 15:37
 */
// subtask_60.cpp：按人扫描序列，双重循环枚举所有合法连续子序列（最坏 O(L^2)），
// 不显式存边，适合 sum(l) <= 2000、r <= 10 的测试点。
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 200005;   // 值的范围
const int MAXR = 105;      // 询问中的最大轮数不超过 100

// 一个询问：恰好 r 轮接龙后，最后一个元素是否恰好为 v
struct Query {
    int r;
    int v;
};

int n, k, q;
int max_round;              // 所有询问中的最大轮数

vector<vector<int> > seq;   // seq[person] = 第 person 个人的序列，下标从 1 开始用
vector<Query> queries;      // 全部询问

// reachable[r][v]：第 r 轮结束时值 v 是否可达
bool reachable[MAXR][MAXV];

// ---------- 轮次状态 ----------
// last1[v]：值 v 在上一轮的第一个生产者
// last2[v]：值 v 在上一轮的第二个生产者（同一轮中另一个不同的人）
// -1 不可达，0 第 0 轮（初始状态，任何人都可用）
int last1[MAXV], last2[MAXV];
int next1[MAXV], next2[MAXV];

// 读入一组数据，并求出询问中的最大轮数。
void read_input() {
    cin >> n >> k >> q;

    seq.assign(n + 1, vector<int>());
    for (int person = 1; person <= n; person++) {
        int len;
        cin >> len;
        seq[person].resize(len + 1);   // 下标 0 不用，方便和题面下标对应
        for (int i = 1; i <= len; i++) {
            cin >> seq[person][i];
        }
    }

    queries.resize(q + 1);
    max_round = 0;
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].r >> queries[i].v;
        max_round = max(max_round, queries[i].r);
    }
}

// 判断值 v 是否可以作为本轮 person 的开头：
// 上轮必须有人以 v 结尾，且本轮的人不能与上轮第一生产者相同
// 除非上轮还有另一个不同的人也以 v 结尾
bool can_start(int v, int person) {
    if (last1[v] == -1) return false;
    if (last1[v] == 0) return true;
    if (last1[v] != person) return true;
    return last2[v] != -1;
}

// 记录“本轮可以由 person 接到 value”。
// 每个值只保留两个不同的人，已经足够判断下一轮能否换人。
void add_next_state(int value, int person) {
    if (next1[value] == -1) {
        next1[value] = person;
    } else if (next1[value] != person && next2[value] == -1) {
        next2[value] = person;
    }
}

// 固定本轮接龙人，双重循环枚举他的所有合法接龙序列 seq[person][left..right]。
void scan_person(int person, int round) {
    vector<int>& s = seq[person];
    int len = (int)s.size() - 1;

    for (int left = 1; left <= len; left++) {
        int from_value = s[left];
        if (!can_start(from_value, person)) continue;

        // 接龙序列长度必须在 [2, k]，所以结尾 right ∈ [left + 1, left + k - 1]
        int right_end = min(len, left + k - 1);
        for (int right = left + 1; right <= right_end; right++) {
            int to_value = s[right];
            add_next_state(to_value, person);
            reachable[round][to_value] = true;
        }
    }
}

// 从上一轮状态计算指定轮的全部可达状态。
void transfer_one_round(int round) {
    memset(next1, -1, sizeof(next1));
    memset(next2, -1, sizeof(next2));

    for (int person = 1; person <= n; person++) {
        scan_person(person, round);
    }

    memcpy(last1, next1, sizeof(last1));
    memcpy(last2, next2, sizeof(last2));
}

void preprocess_answers() {
    memset(last1, -1, sizeof(last1));
    memset(last2, -1, sizeof(last2));
    memset(reachable, 0, sizeof(reachable));

    // 第 0 轮从值 1 开始，0 表示还没有真正的上一轮接龙人。
    last1[1] = 0;

    for (int round = 1; round <= max_round; round++) {
        transfer_one_round(round);
    }
}

void print_answers() {
    for (int i = 1; i <= q; i++) {
        cout << (reachable[queries[i].r][queries[i].v] ? 1 : 0) << '\n';
    }
}

void solve() {
    read_input();
    preprocess_answers();
    print_answers();
}

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

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

复杂度与瓶颈

每轮枚举边的复杂度为 $O(E+V)$ ，轮次 DP 总计 $O(R(E+V))$ ，回答询问为 $O(q)$ ；边不落地保存，空间复杂度为 $O(RV+V+L)$ ，最坏 $E=O(L^2)$ 。

这一层已经消除了查询数 $q$ 带来的重复计算，也消除了“上一轮接龙人”这一大维状态。剩下的唯一瓶颈是 $E$ ：完整数据中，一个长度为 $2\times10^5$ 的序列可能产生平方级别的边，逐一枚举根本做不完。

性质 B 恰好暴露了这个瓶颈。当 $k\leqslant5$ 时， $E=O(kL)=O(L)$ ，逐一枚举边重新变得可行；但要统一通过所有数据，仍需让每轮转移不依赖 $E$ 。

正解

关键观察一：两个接龙人已经足够

设 $P_t(v)$ 为恰好完成 $t$ 轮并以 $v$ 结尾时，最后一轮所有可能的接龙人集合。

下一轮若准备选择人 $p$ ，只需判断

\exists x\in P_t(v),\quad x\neq p

这个判断只关心集合是空、只有 $p$ ，还是存在另一个人。因此保存任意两个不同的代表人，就能得到与完整集合完全相同的判断结果。

代码使用：

last1[v]、last2[v]：上一轮到达 $v$ 的两个不同代表人；
next1[v]、next2[v]：本轮到达 $v$ 的两个不同代表人；
-1：不存在；
0：第 $0$ 轮的虚拟接龙人。

这一观察继承自 $60$ 分做法，没有改变。

关键观察二：一批边其实是一个位置区间

固定接龙人 $p$ ，从左到右扫描 $S_p$ 。如果位置 $i$ 的值能作为本轮起点，那么它能够到达的结尾位置恰好为

[i+1,\min(l_p,i+k-1)]

逐一枚举有色边会逐个检查区间中的所有位置。其实只需维护当前被至少一个合法起点覆盖的区间。

扫描到位置 pos 时：

用上一轮的两个代表人判断 S[p][pos] 能否由人 $p$ 作为本轮起点；
若能，就把新区间 $[pos+1,\min(l_p,pos+k-1)]$ 合并进当前覆盖范围；
若 pos 在覆盖范围中，它就是本轮的合法结尾，把人 $p$ 加入 S[p][pos] 的下一轮代表人集合。

为什么只维护一个当前区间就够？为什么合并后一定是连续的？

按整数数轴来看：新起点 $pos$ 产生的覆盖区间左端点恰好是 $pos + 1$ 。旧区间的右端点只要满足 range_end >= pos，合并就绝对不会断开：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16情况 1：range_end > pos（有重叠，无缝连通）
旧区间覆盖:  [-----------------] (到 pos+1 或更远)
新区间覆盖:              [pos+1 --------------->
合并结果:    [--------------------------------->

情况 2：range_end == pos（刚好相邻，无缝拼接）
旧区间覆盖:  [--------- pos]
新区间覆盖:                 [pos+1 ------------->
合并结果:    [----------------------------------->
注：pos 与 pos+1 是两个相邻整数，中间没有空隙！

情况 3：range_end < pos（真正断开）
旧区间覆盖:  [--- range_end]  (已在 pos 之前结束)
                      ... 空隙 ...
新区间覆盖:                           [pos+1 --->
处理方式:    旧区间已在身后过期，直接舍弃，以 [pos+1, new_end] 作为全新区间。

因此：

只要 range_end >= pos，旧区间和新区间要么重叠、要么紧紧贴在一起，合并后必定是连续的一整段闭区间；
只有 range_end < pos 时才会出现断层，而此时旧区间已经完全落后于当前扫描位置，直接重开即可。

这一步把每轮的 $O(E)$ 降为扫描所有序列一次的 $O(L)$ 。

完整转移

先读入全部询问并求出 $R$ ，然后：

初始化 last1[1] = 0，其余值不可达；
枚举轮数 $t=1,2,\ldots,R$ ；
清空本轮的 next1、next2；
依次扫描每个人的完整序列，用覆盖区间批量完成本轮转移；
记录第 $t$ 轮的所有可达结尾值；
把 next 数组变成下一轮的 last 数组。

于是每个询问 $(r,c)$ 都能 $O(1)$ 回答。

样例中的第一轮

样例的三个序列为 $[1,2,3,4,1]$ 、 $[1,2,5]$ 、 $[5,1,6]$ ，且 $k=3$ 。第 $0$ 轮只有状态 $P_0(1)=\{0\}$ 。

下面的表格展示“合法起点覆盖一段结尾位置”的过程。

接龙人	合法起点	覆盖的结尾位置	产生的 $(结尾值,接龙人)$
$1$	第 $1$ 位的 $1$	第 $2\sim3$ 位	$(2,1),(3,1)$
$2$	第 $1$ 位的 $1$	第 $2\sim3$ 位	$(2,2),(5,2)$
$3$	第 $2$ 位的 $1$	第 $3$ 位	$(6,3)$

所以第一轮结束后：

结尾值 $v$	保存的代表人
$2$	$\{1,2\}$
$3$	$\{1\}$
$5$	$\{2\}$
$6$	$\{3\}$

值 $2$ 保存两个代表人后，下一轮无论选择人 $1$ 还是人 $2$ ，都能从另一个代表人的方案接过来；而值 $3$ 只有代表人 $1$ ，所以下一轮不能继续选择人 $1$ 。

正确性说明

对轮数 $t$ 归纳。

归纳假设：last1[v]、last2[v] 足以正确判断是否存在恰好 $t-1$ 轮到达 $v$ 、且最后一轮接龙人不等于任意给定人 $p$ 的方案。

固定本轮接龙人 $p$ 。扫描 $S_p$ 时，一个位置 $i$ 被判为合法起点，当且仅当上一轮能到达 $S_{p,i}$ ，并且存在一个代表人不等于 $p$ 。根据归纳假设，这与游戏的换人规则完全等价。

每个合法起点 $i$ 覆盖且只覆盖 $i+1$ 到 $\min(l_p,i+k-1)$ ，正好对应长度在 $[2,k]$ 内的全部连续子序列。因此扫描得到的结尾位置不多不少。把当前人 $p$ 记入结尾值的代表集合后，就得到本轮所有合法方案。

若某个结尾值有至少两个不同接龙人，保留任意两个后，对任意下一轮接龙人仍至少有一个代表人与他不同；若只有一个人，则必须保留这个人。故压缩不会改变下一轮的任何可行性判断，归纳成立。

初始状态 last1[1] = 0 正确表示游戏从值 $1$ 开始且尚无上一轮接龙人，所以算法对所有轮数均正确。

代码

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158/**
 * 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-07-05 21:47
 * update_at: 2026-10-01 15:36
 */
// main.cpp：按人扫描序列做轮次 DP，用覆盖区间批量标记可达值。
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 200005;   // 值的范围
const int MAXR = 105;      // 询问中的最大轮数不超过 100

// 一个询问：恰好 r 轮接龙后，最后一个元素是否恰好为 v
struct Query {
    int r;
    int v;
};

int n, k, q;
int max_round;              // 所有询问中的最大轮数

vector<vector<int> > seq;   // seq[person] = 第 person 个人的序列，下标从 1 开始用
vector<Query> queries;      // 全部询问

// reachable[r][v]：第 r 轮结束时值 v 是否可达
bool reachable[MAXR][MAXV];

// ---------- 轮次状态 ----------
// last1[v]：值 v 在上一轮的第一个生产者
// last2[v]：值 v 在上一轮的第二个生产者（同一轮中另一个不同的人）
// -1 不可达，0 第 0 轮（初始状态，任何人都可用）
int last1[MAXV], last2[MAXV];
int next1[MAXV], next2[MAXV];

// 读入一组数据，并求出询问中的最大轮数。
void read_input() {
    cin >> n >> k >> q;

    seq.assign(n + 1, vector<int>());
    for (int person = 1; person <= n; person++) {
        int len;
        cin >> len;
        seq[person].resize(len + 1);   // 下标 0 不用，方便和题面下标对应
        for (int i = 1; i <= len; i++) {
            cin >> seq[person][i];
        }
    }

    queries.resize(q + 1);
    max_round = 0;
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].r >> queries[i].v;
        max_round = max(max_round, queries[i].r);
    }
}

// 判断值 v 是否可以作为本轮 person 的开头：
// 上轮必须有人以 v 结尾，且本轮的人不能与上轮第一生产者相同
// 除非上轮还有另一个不同的人也以 v 结尾
bool can_start(int v, int person) {
    if (last1[v] == -1) return false;
    if (last1[v] == 0) return true;
    if (last1[v] != person) return true;
    return last2[v] != -1;
}

// 记录“本轮可以由 person 接到 value”。
// 每个值只保留两个不同的人，已经足够判断下一轮能否换人。
void add_next_state(int value, int person) {
    if (next1[value] == -1) {
        next1[value] = person;
    } else if (next1[value] != person && next2[value] == -1) {
        next2[value] = person;
    }
}

// 固定本轮接龙人，扫描他的整个序列。
void scan_person(int person, int round) {
    vector<int>& s = seq[person];
    int len = (int)s.size() - 1;

    int range_start = 1;
    int range_end = 0;

    for (int pos = 1; pos <= len; pos++) {
        int value = s[pos];

        // 合法起点 pos 能覆盖后面的 [pos + 1, pos + k - 1]。
        if (can_start(value, person)) {
            int new_end = min(len, pos + k - 1);
            if (range_end < pos) {
                range_start = pos + 1;
                range_end = new_end;
            } else {
                range_end = max(range_end, new_end);
            }
        }

        // pos 被某个更早的合法起点覆盖，因此能作为本轮结尾。
        if (pos >= range_start && pos <= range_end) {
            add_next_state(value, person);
            reachable[round][value] = true;
        }
    }
}

// 从上一轮状态计算指定轮的全部可达状态。
void transfer_one_round(int round) {
    memset(next1, -1, sizeof(next1));
    memset(next2, -1, sizeof(next2));

    for (int person = 1; person <= n; person++) {
        scan_person(person, round);
    }

    memcpy(last1, next1, sizeof(last1));
    memcpy(last2, next2, sizeof(last2));
}

void preprocess_answers() {
    memset(last1, -1, sizeof(last1));
    memset(last2, -1, sizeof(last2));
    memset(reachable, 0, sizeof(reachable));

    // 第 0 轮从值 1 开始，0 表示还没有真正的上一轮接龙人。
    last1[1] = 0;

    for (int round = 1; round <= max_round; round++) {
        transfer_one_round(round);
    }
}

void print_answers() {
    for (int i = 1; i <= q; i++) {
        cout << (reachable[queries[i].r][queries[i].v] ? 1 : 0) << '\n';
    }
}

void solve() {
    read_input();
    preprocess_answers();
    print_answers();
}

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

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

两个代表人还可以合并成一个整数编码：last[v] = p 表示上一轮只有人 $p$ 到达 $v$ ，下一轮只要换人就能从 $v$ 开头；last[v] = 0 表示上一轮至少有两个不同的人到达 $v$ ，谁都能接着开头；-1 表示不可达。第 $0$ 轮的初始状态 last[1] = 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
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157/**
 * 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 15:46
 * update_at: 2026-10-01 15:46
 */
// main_no_last2.cpp：main.cpp 的简化版，只用一个 last[v] 记录上一轮接龙人，
// 不再分开保存 last1 / last2。扫描窗口做法不变。
//
// last[v] 的编码：
//   -1     ：值 v 不可达，谁都不能拿它开头；
//    0     ：上一轮至少有两个不同的人到达 v（或第 0 轮的初始值 1），
//            下一轮任何人都可以拿它开头；
//    p (>=1)：上一轮只有人 p 到达 v，下一轮只有 p 不能拿它开头。
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 200005;   // 值的范围
const int MAXR = 105;      // 询问中的最大轮数不超过 100

// 一个询问：恰好 r 轮接龙后，最后一个元素是否恰好为 v
struct Query {
    int r;
    int v;
};

int n, k, q;
int max_round;              // 所有询问中的最大轮数

vector<vector<int> > seq;   // seq[person] = 第 person 个人的序列，下标从 1 开始用
vector<Query> queries;      // 全部询问

// reachable[r][v]：第 r 轮结束时值 v 是否可达
bool reachable[MAXR][MAXV];

// ---------- 轮次状态 ----------
int last[MAXV];             // 上一轮状态，编码见文件头
int next_last[MAXV];          // 本轮状态，扫描完再整体复制到 last

// 读入一组数据，并求出询问中的最大轮数。
void read_input() {
    cin >> n >> k >> q;

    seq.assign(n + 1, vector<int>());
    for (int person = 1; person <= n; person++) {
        int len;
        cin >> len;
        seq[person].resize(len + 1);   // 下标 0 不用，方便和题面下标对应
        for (int i = 1; i <= len; i++) {
            cin >> seq[person][i];
        }
    }

    queries.resize(q + 1);
    max_round = 0;
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].r >> queries[i].v;
        max_round = max(max_round, queries[i].r);
    }
}

// 判断值 v 是否可以作为本轮 person 的开头。
bool can_start(int v, int person) {
    if (last[v] == -1) return false;   // 不可达
    if (last[v] == 0) return true;     // 至少两个不同的人（或初始状态）
    return last[v] != person;          // 唯一生产者不是 person 才行
}

// 记录“本轮可以由 person 接到 value”。
// 只有一个生产者时记下他，出现第二个不同的人就改记 0。
void add_next_laststate(int value, int person) {
    if (next_last[value] == -1) {
        next_last[value] = person;
    } else if (next_last[value] != person) {
        next_last[value] = 0;
    }
}

// 固定本轮接龙人，扫描他的整个序列。
void scan_person(int person, int round) {
    vector<int>& s = seq[person];
    int len = (int)s.size() - 1;

    int range_start = 1;
    int range_end = 0;

    for (int pos = 1; pos <= len; pos++) {
        int value = s[pos];

        // 合法起点 pos 能覆盖后面的 [pos + 1, pos + k - 1]。
        if (can_start(value, person)) {
            int new_end = min(len, pos + k - 1);
            if (range_end < pos) {
                range_start = pos + 1;
                range_end = new_end;
            } else {
                range_end = max(range_end, new_end);
            }
        }

        // pos 被某个更早的合法起点覆盖，因此能作为本轮结尾。
        if (pos >= range_start && pos <= range_end) {
            add_next_laststate(value, person);
            reachable[round][value] = true;
        }
    }
}

// 从上一轮状态计算指定轮的全部可达状态。
void transfer_one_round(int round) {
    memset(next_last, -1, sizeof(next_last));

    for (int person = 1; person <= n; person++) {
        scan_person(person, round);
    }

    memcpy(last, next_last, sizeof(last));
}

void preprocess_answers() {
    memset(last, -1, sizeof(last));
    memset(reachable, 0, sizeof(reachable));

    // 第 0 轮从值 1 开始，且还没有真正的上一轮接龙人，
    // 任何人开头都可以，正好用 0 表示。
    last[1] = 0;

    for (int round = 1; round <= max_round; round++) {
        transfer_one_round(round);
    }
}

void print_answers() {
    for (int i = 1; i <= q; i++) {
        cout << (reachable[queries[i].r][queries[i].v] ? 1 : 0) << '\n';
    }
}

void solve() {
    read_input();
    preprocess_answers();
    print_answers();
}

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

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

同一算法的 Python 版本见下。生产者编码与 main_no_last2.cpp 相同（ANY = 0 表示至少两个不同的人，谁都能接着开头），区别在于：用字典代替值域数组，只记录出现过的值；询问按轮数分桶，算完第 $t$ 轮就地回答；某一轮没有任何值可达时，后面的轮数直接跳过。

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#!/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-09-28 16:40
# update_at: 2026-09-28 16:40

import sys
from collections import defaultdict
from collections.abc import Iterator

ANY = 0  # 生产者编码：0 = 至少两个人可以接（第 0 轮的值 1 也记成它）

# 类型别名（Python 3.12+ 的 type 语句），相当于 C++ 的 using / typedef
type PrevMap = dict[int, int]    # 上一轮/本轮的"值 -> 生产者编码"
type Seqs = list[list[int]]      # 每个人的序列


def reachable_values(seq: list[int], person: int, k: int, prev: PrevMap) -> Iterator[int]:
    """依次产出本轮这个人能收尾的值（同一个值的多次出现会重复产出）。

    合法起点 pos 覆盖结尾位置 [pos+1, pos+k-1]。起点从左往右扫，pos+k-1 单调递增，
    所以"覆盖到哪"只需一个 deadline，不必记录整段区间。
    """
    deadline = 0
    for pos, value in enumerate(seq, 1):
        covered = pos <= deadline                      # 更早的合法起点已经覆盖到 pos
        if covered:
            yield value
        can_start = prev.get(value, person) != person  # 上一轮到过 value，且不是只有自己
        if can_start:
            deadline = pos + k - 1                     # 从 pos 出发能延伸到的最右位置


def advance(prev: PrevMap, seqs: Seqs, k: int) -> PrevMap:
    """由第 r-1 轮可达状态推出第 r 轮状态：合并所有人的可达值。"""
    nxt: PrevMap = {}
    for person, seq in enumerate(seqs, 1):
        for value in reachable_values(seq, person, k, prev):
            # 登记生产者：本轮首次出现 value、或唯一生产者还是自己 → person，否则 ANY
            nxt[value] = person if nxt.setdefault(value, person) == person else ANY
    return nxt


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n, k, q = next(data), next(data), next(data)

        seqs: Seqs = []
        for _ in range(n):
            length = next(data)  # 题面的 l_i
            seqs.append([next(data) for _ in range(length)])

        # 询问按轮数分桶，桶里存 (原始下标, 结尾值)，这样结果能按输入顺序输出。
        by_round = defaultdict(list)
        for i in range(q):
            r, c = next(data), next(data)
            by_round[r].append((i, c))

        ans = [0] * q
        prev: PrevMap = {1: ANY}  # 第 0 轮只有值 1，且没有上一轮的接龙人
        max_round = max(by_round)        # max(dict) 迭代的是 key，最大 key 就是最大轮数
        for rnd in range(1, max_round + 1):
            prev = advance(prev, seqs, k)
            for i, c in by_round[rnd]:
                ans[i] = 1 if c in prev else 0
            if not prev:  # 这一轮一个值都到不了，后面永远都到不了
                break

        out += map(str, ans)

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

每一轮扫描全部 $L$ 个序列元素，并清空、复制值域状态数组，时间复杂度为

O(R(L+V)+q)

保存所有轮数的询问答案需要 $O(RV)$ 空间，滚动的代表人状态与所有人的序列存储需要 $O(V+L)$ 空间，因此总空间复杂度为

O(RV+V+L)

在完整范围 $R\leqslant100$ 、 $L,V\leqslant2\times10^5$ 下可以通过。

总结

这道题的数据层次对应两个独立瓶颈：

搜索会对不同询问重复计算，于是改成按轮数预处理；
记录全部上一轮接龙人太大，于是每个值只留两个不同代表人；
显式连续子序列边可能达到平方级，于是把一个起点的全部出边看成位置区间，用一次线性扫描批量转移。

因此， $15$ 分搜索、 $60$ 分逐边枚举 DP 和 $100$ 分扫描 DP 并不是互不相关的三套算法。后一层始终保留前一层的有色边模型，只针对刚刚暴露出的瓶颈做一次压缩；这才是各数据范围之间真正的递进关系。

P11230 [CSP-J 2024] 接龙

题目描述

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

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

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

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

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

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $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$ ，描述一个任务。

输出格式

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

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
10
11
121
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

text

说明/提示

【样例 1 解释】

在下文中，我们使用 $\{A_i\} = \{A_1, A_2, \dots , A_r\}$ 表示一轮游戏中所有的接龙序列， $\{p_i\} = \{p_1, p_2, \dots , 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$ ，因此任务显然不可完成。

【样例 2】

见选手目录下的 chain/chain2.in 与 chain/chain2.ans。

该样例满足测试点 1 的特殊性质。

【样例 3】

见选手目录下的 chain/chain3.in 与 chain/chain3.ans。

该样例满足测试点 2 的特殊性质。

【样例 4】

见选手目录下的 chain/chain4.in 与 chain/chain4.ans。

该样例满足特殊性质 A，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【样例 5】

见选手目录下的 chain/chain5.in 与 chain/chain5.ans。

该样例满足特殊性质 B，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【样例 6】

见选手目录下的 chain/chain6.in 与 chain/chain6.ans。

该样例满足特殊性质 C，其中前两组测试数据满足 $n \leq 1000$ 、 $r \leq 10$ 、单组测试数据内所有词库的长度和 $\leq 2000$ 、 $q \leq 1000$ 。

【数据范围】

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

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

::cute-table{tuack}

测试点	$n\leq$	$r\leq$	$\sum l\leq$	$q\leq$	特殊性质
$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$	^
$7,8$	$10^3$	$10$	$2000$	$10^3$	B
$9,10$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	^
$11,12$	$10^3$	$10$	$2000$	$10^3$	C
$13,14$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	^
$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 ≤ 5$ 。

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

[CSP-J 2024] 接龙

目录

形式化题目

解法路线

子任务解法：r=1r=1r=1

适用范围

思路

代码

复杂度与瓶颈

暴力解法：L⩽20L\leqslant20L⩽20

适用范围

思路

代码

复杂度与瓶颈

子任务解法：L⩽2000,R⩽10L\leqslant2000,R\leqslant10L⩽2000,R⩽10

适用范围

思路

代码

复杂度与瓶颈

正解

关键观察一：两个接龙人已经足够

关键观察二：一批边其实是一个位置区间

完整转移

样例中的第一轮

正确性说明

代码

复杂度

总结

子任务解法： $r=1$

暴力解法： $L\leqslant20$

子任务解法： $L\leqslant2000,R\leqslant10$