GESP 题解库 / 8 级题解 / [GESP202403 八级] 接竹竿 · 第 17 / 24 题
GESP202403 八级 · P10264 · 困难

接竹竿:队里永不重复

同一个左端点只模拟一次;队列长度恒 ≤ 13,每放一张牌只要 O(1)。

🃏
n, q ≤ 1.5 × 10⁴
牌数 / 询问数
🔢
1 ≤ Aᵢ ≤ 13
点数只有 13 种
⚡
队列长度 ≤ 13
每次操作 O(1)
🎯
按左端点分组模拟
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨同学想用卡牌玩一种叫做"接竹竿"的游戏。

游戏规则是:每张牌上有一个点数 v,将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌,则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列(包括这两张牌本身)。

小杨同学现在有一个长度为 n 的卡牌序列 A,其中每张牌的点数为 Aᵢ(1 ≤ i ≤ n)。小杨同学有 q 次询问。第 i 次(1 ≤ i ≤ q)询问时,小杨同学会给出 lᵢ, rᵢ,想知道如果用下标在 [lᵢ, rᵢ] 的所有卡牌按照下标顺序玩"接竹竿"的游戏,最后队列中剩余的牌数。

输入格式:一行包含一个正整数 T,表示测试数据组数。对于每组测试数据,第一行包含一个正整数 n,表示卡牌序列 A 的长度;第二行包含 n 个正整数 A₁, A₂, …, Aₙ;第三行包含一个正整数 q,表示询问次数;接下来 q 行,每行两个正整数 lᵢ, rᵢ,表示一组询问。

输出格式:对于每组数据,输出 q 行。第 i 行输出一个非负整数,表示第 i 次询问的答案。

输入输出样例

样例内容
输入 #11
6
1 2 2 3 1 3
4
1 3
1 6
1 5
5 6
输出 #11
1
0
2
样例解释(第 1 次询问)按 1, 2, 2 的顺序放牌,放最后一张时两张点数为 2 的牌一起被收走,最后只剩一张点数为 1 的牌
样例解释(第 2 次询问)队列变化为 { } → {1} → {1,2} → {1,2,2} → {1} → {1,3} → {1,3,1} → { } → {3},最后只剩一张点数为 3 的牌
💡
人话翻译:把 A_l, A_{l+1}, …, A_r 按顺序往队尾放,一旦放下的点数在队里已经存在,就把"那一张"连同它后面所有的牌一起抽走。问最后队里剩几张牌。
最关键的观察是:队列里永远不可能有两张点数相同的牌——因为只要撞上重复点数,撞到的那一段就全被抽走了。
而点数一共只有 13 种,于是队列长度恒 ≤ 13,"放一张牌"这件事可以做到 O(1)。
再把询问按左端点 l 分组:左端点相同的询问可以共享同一次"从头放牌"的过程,只要多记一个"扫到哪个位置时队里有几张牌"就行了。

🔍 关键词提取

模拟队列队列内无重复按左端点离线分组状态很窄就能重放

已知条件

项目说明
输入第一行 T;每组数据:n、n 个点数、q、q 行 l r
输出每组 q 行,每行是该询问最后剩余的牌数
数据范围1 ≤ T ≤ 5,1 ≤ n ≤ 1.5 × 10⁴,1 ≤ q ≤ 1.5 × 10⁴
点数范围1 ≤ Aᵢ ≤ 13(只有 13 种)
子任务30 分:n, q ≤ 100;30 分:所有询问的 rᵢ = n;40 分:完整数据
答案范围队列长度落在 [0, 13] 内

需要解决的问题

02
思维导图
整理解题思路的全貌
🃏 每个左端点开一局,最多扫到最远的 r
🧠 关键性质
队列中永远不会有重复点数
因为撞点会把它到队尾全部收走
⟹ 队列长度恒 ≤ 13
⟹ 每放一张牌都是 O(1)
📥 输入与分组
T 组数据各自独立
把 q 个询问按左端点 l 分组
每组记下该组最大的 r = maxr
从空队开始依次放 A_l … A_maxr
🔁 单步维护
pos[v] = v 在队中的下标(1 起)
pos[v] = 0 表示 v 不在队里
撞点:队尾截断到 pos[v] − 1 并清 pos
否则入队并令 pos[v] = 新队长
扫到某个 r 就记下当时的队长
⚠️ 易错点
撞点后忘记清被删牌的 pos
每个询问都重开一局(重复扫描)
队列数组只开 13 而不留余量
多组数据忘清 ask / ans
03
样例手算推导
样例 {1,2,2,3,1,3} 的逐步过程

🧮 样例逐步手算:四次询问的队列变化

序列 A = 1 2 2 3 1 3(下标 1 ~ 6)。注意第 2 次询问题面已经给出了完整的队列变化序列,我们把它和另外三次一起摊开看。

第 2 次询问:l = 1, r = 6(从头放到尾)

步骤放入队中已有同点数吗队列队长
1A₁ = 1没有{1}1
2A₂ = 2没有{1, 2}2
3A₃ = 2有(下标 2){1}1
4A₄ = 3没有{1, 3}2
5A₅ = 1有(下标 1){ }0
6A₆ = 3没有{3}1
1
第 1 次询问:l = 1, r = 3

只需要第 2 次询问的前 3 步

{1} → {1, 2} → {1}

第 3 步放 A₃ = 2 时撞上队中的 2(下标 2)

把下标 2 到队尾取走,只剩 {1}

✅ 答案 1

2
第 3 次询问:l = 1, r = 5

只需要第 2 次询问的前 5 步

{1} → {1, 2} → {1} → {1, 3} → { }

第 5 步放 A₅ = 1 时撞上队中的 1(下标 1)

从下标 1 到队尾全部取走,队列清空

✅ 答案 0

3
第 4 次询问:l = 5, r = 6

左端点变成 5,必须从 A₅ 重新开一局(不能沿用前面的队列)

放 A₅ = 1 → {1}(队里没有 1)

放 A₆ = 3 → 队里没有 3,直接入队 → {1, 3}

两张点数不同,谁也没撞上谁

✅ 答案 2

🔑
把 4 个答案和题面核对一下:1 / 1 / 0 / 2,与样例输出完全一致。
特别留意第 4 次询问:A₅ = 1 这张牌在 l = 1 的那一局里曾把整条队列清空,但在 l = 5 这一局里它只是"第一张牌"。
同一张牌在不同询问里的作用完全不同,这就是"每个左端点必须单独开一局"的原因。

🧩 三个"为什么":性质、分组、答案范围

为什么队列里永远不会出现两张同点数的牌?

时刻队列接下来放入会发生什么
刚放完 1、2{1, 2}放入 2队列变成 {1, 2, 2},出现重复
放入的瞬间{1, 2, 2}按规则取走"已有的 2 到队尾"变成 {1},重复立刻消失
1
性质一:队中每种点数最多一张(于是队长 ≤ 13)

设放入 v 之前,队中已经存在一张 v

规则要求把"已有的那张 v"到队尾全部取出(含两端)

取出后,队中既没有旧的 v,也没有新放的 v

所以任何时刻,每种点数在队中最多出现一次

点数一共只有 1…13 共十三种 ⟹ 队列长度恒 ≤ 13

推论:答案一定落在 [0, 13] 之内

✅ 队长 ≤ 13,这是"每次操作 O(1)"的基础

2
性质二:固定左端点后,队列状态是"确定"的

固定 l,依次放入 A_l, A_{l+1}, …

放完 A_l … A_i 之后的队列,只由 A_l … A_i 决定

与"后面还会放什么牌"完全无关

所以同一个 l 的所有询问可以共用这一次扫描

扫到 i = r 的那一刻把当前队长记下来即可

✅ 这是"按左端点分组"的正确性依据

3
性质三:只需扫到该组最大的 r

同一组里 r 较小的询问,扫到它时就能立即回答

r 最大的那个询问决定了这次扫描要走多远

所以只扫到 maxr,剩下的位置本组再也用不到

不会漏答:每个询问的 r 都 ≤ maxr,

扫过它的那一刻答案已经记下

✅ 这是"只扫到 maxr"的正确性依据

⚠️
两个非常容易踩的坑:
· 撞点截断队尾之后,一定要把被取走那些牌的 pos 清 0,否则下次还会以为它们留在队里;
· 别把"每个询问都要重放"简化成"每组数据只重放一次"——不同 l 的起始状态完全不同,必须按 l 各开一局;同一局里则按 r 从小到大边扫边答,扫到 maxr 才收工。
04
解法对比
按左端点分组 + 增量模拟 vs 每个询问独立重放

⚔️ 解法对比

🟢 按左端点分组 + 增量模拟(推荐) 推荐

把询问按 l 分组,同一个 l 只从空队开始扫一次,扫到各组最大 r 为止

  • 单组最坏约 n(n+1)/2 ≈ 1.1 × 10⁸ 次操作
  • 每次操作 O(1)(队列长 ≤ 13)
  • 空间 O(n + q),代码约 45 行
  • 覆盖全部子任务
💡
省在哪里:如果每个询问都重放一遍,同一个 l 的前缀会被反复扫描很多次;分组后每个 l 只扫一遍,而且只扫到"本组最远的 r",不会白扫后面用不到的位置。

🟠 每个询问独立重放

对每个 (l, r) 都从 A_l 开始放到 A_r,直接输出队长

  • 单组最坏 q × n = 2.25 × 10⁸ 次操作
  • 每次操作同样 O(1)
  • 写法最直白,几乎不会写错
  • T = 5 组时总额约 1.1 × 10⁹,偏险
⚠️
它也有活路:因为每次"放牌"确实只要 O(1)(撞点后最多清 13 个 pos),很多选手就这么写并拿到了分;但 5 组数据叠加后常数大的实现容易 TLE。
分组法把同一左端点的重复劳动直接消掉,稳妥得多。

📈 性能对比

方案复杂度结论
按左端点分组 + 增量模拟单组 ≤ Σ(maxr − l + 1) ≈ 1.1 × 10⁸✅ 推荐
每个询问独立重放单组 ≤ q × n = 2.25 × 10⁸⚠️ 能过但偏险
每个询问重放 + 每步线性找同点数单组 ≤ q × n × n❌ 必然 TLE
05
算法流程图
按左端点分组模拟的主流程
开始读入 T;逐组读入 n、卡牌序列 A、q 与 q 个询问把询问按左端点 l 分组,每组记下最大的 r取下一个未处理的 l:队列清空,pos[1…13] 全部置 0依次放入 A_l … A_maxr,每放一张只花 O(1)队中已有这个点数吗?有 ✓从 pos[v] 到队尾全部取走无 ✗压入队尾并记 pos[v]当前位置是某个询问的 r 吗?是 ✓把当前队长记为该询问答案否 ✗什么也不做还有左端点没处理完吗?按询问顺序输出 q 个答案换下一个 l
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🃏 接竹竿模拟器

第一行 n;第二行 n 个点数(1 ~ 13);第三行 q;随后 q 行 l r。程序按左端点分组建模,展示队列的逐步变化与每次询问的答案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(按左端点分组 + O(1) 维护队列)

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 13;      // 点数只有 1…13

int T, n, q;
int A[15005];
vector<pair<int, int> > ask[15005];   // ask[l] 存放左端点为 l 的询问 (r, 编号)
int ans[15005];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
        scanf("%d", &q);
        for (int i = 1; i <= n; i++) ask[i].clear();   // 多测:清空分组
        for (int i = 1; i <= q; i++) {
            int l, r;
            scanf("%d %d", &l, &r);
            ask[l].push_back(make_pair(r, i));
        }

        for (int l = 1; l <= n; l++) {
            if (ask[l].empty()) continue;
            int maxr = 0;                              // 本组只需要扫到这里
            for (int i = 0; i < (int)ask[l].size(); i++)
                maxr = max(maxr, ask[l][i].first);
            vector<pair<int, int> > cur = ask[l];
            sort(cur.begin(), cur.end());               // 按 r 升序,边扫边回答

            int que[MAXV + 5];                          // 队列(1 起),长度恒 ≤ 13
            int pos[MAXV + 1];                          // pos[v] = v 在队中的下标,0 表示不在
            for (int v = 0; v <= MAXV; v++) pos[v] = 0;
            int tail = 0, head = 0;

            for (int i = l; i <= maxr; i++) {
                int v = A[i];
                if (pos[v] != 0) {
                    int cut = pos[v];                   // 先记下位置!
                    // 把 cut … tail 一起取走,并同步清空它们的 pos
                    for (int j = cut; j <= tail; j++) pos[que[j]] = 0;
                    tail = cut - 1;                     // 队尾截断到 cut - 1
                } else {
                    que[++tail] = v;                    // 入队
                    pos[v] = tail;
                }
                while (head < (int)cur.size() && cur[head].first == i) {
                    ans[cur[head].second] = tail;       // 扫到 r 就记下当前队长
                    head++;
                }
            }
        }

        for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    }
    return 0;
}
🔑
三个要点:① pos 是本题的灵魂——它把"找到点数相同的牌在哪"变成了一次数组取值;② 截断队尾时必须同步清空被删元素的 pos,否则下次会误以为它还留在队里;③ 多组数据要把 ask[] 清干净,否则上一组的询问会污染下一组。

📖 关键几行怎么看

代码作用为什么这样写
ask[l].push_back(make_pair(r, i))按左端点分组同一个 l 的询问共享一次模拟
maxr = max(maxr, ask[l][i].first);只扫到最远的 r后面的位置本组用不到,不必白扫
if (pos[v] != 0)判断是否撞点O(1) 知道队里有没有 v
int cut = pos[v];先保存位置必须抢先保存——下一行的循环会把 pos[v] 清成 0
for (j = cut; j <= tail; j++) pos[que[j]] = 0;清空 pos + 截断队尾tail = cut - 1; 与它配合完成"取走 cut…队尾"
ans[cur[head].second] = tail;记录答案扫到某个 r 的那个时刻,队长就是答案
⚠️
五个坑:① 撞点后忘了先保存 pos[v]:清 pos 的循环会把 pos[v] 自己也清成 0,若紧接着写 tail = pos[v] - 1 就得到 tail = -1,后面全部答案错乱(这是本题最容易犯的错);② 忘了把被删元素的 pos 清零;③ 只能"扫到本组 maxr",如果只扫到某个较小询问的 r 就停手,后面的询问会答错;④ 队列数组只开 13 个位置(要留余量,至少 14 个);⑤ 多测不清 ask[] / ans[];另外别忘了题意是包含两端一起取走。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1
6
1 2 2 3 1 3
4
1 3
1 6
1 5
5 6
1
1
0
2
题面样例 1:四次询问四种情况
1
1
5
1
1 1
1只有一张牌,队列长度 1
1
2
1 1
1
1 2
0两张同点数,全部被取走
1
3
1 2 3
2
1 3
2 3
3
2
点数全不同:队列不会消,长度就是牌数
1
4
1 2 1 2
1
1 4
1交替撞点:{1,2} 消掉后剩 {2}
1
13
1 2 3 4 5 6 7 8 9 10 11 12 13
1
1 13
13点数互不相同,队长达到上界 13
✅
自查清单:① 队列里真的没有重复点数吗?② 撞点后清 pos 了吗?③ 询问按 l 分组、按 r 排序了吗?④ 多测清空了吗?

🚨 易错点清单

⚠️
忘记清 pos:截断队尾后 pos 里还留着"已经不在队里"的下标,下一次撞点会按错误位置截断,队列瞬间错乱。
⚠️
只扫到某个较小的 r:同一组询问要按 r 排序后边扫边答,不能扫到第一个询问的 r 就停下。
⚠️
数组开小:点数范围是 1…13,pos 与队列数组都要留出余量(≥ 14)。
⚠️
多测污染:T 最多 5 组,每组的 ask[]、ans[] 都要重置。
⚠️
区间含义:取走的是"两张同点数牌之间的所有牌",包含这两张牌本身,别漏掉端点。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(Σ(maxr − l + 1))
空间复杂度
O(n + q + 13)
每次操作
O(1)(队列长 ≤ 13)
单组最坏
约 1.1 × 10⁸ 次

时间怎么算的?

空间都用在哪?

A 数组 O(n);按左端点分组的询问 O(q);队列与 pos 各 14 个位置,因为"队中每种点数最多一张"保证了队长 ≤ 13。总空间只有几 MB。

✅ 单组最坏约 1.1 × 10⁸ 次"极轻量"操作(数组取值与自增),5 组数据合计约 5.6 × 10⁸ 次,常数极小,C++ 实测可通过;这正是本题标程采用的复杂度。关键是把 O(1) 的观察用满:队列短、pos 直接定位、同左端点共享扫描。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ① 按左端点分组的通用骨架
for (int l = 1; l <= n; l++) {
    if (ask[l].empty()) continue;
    int maxr = 0;                        // 本组最远的右端点
    for (auto& pr : ask[l]) maxr = max(maxr, pr.first);
    sort(ask[l].begin(), ask[l].end());   // 按 r 升序
    // 初始状态(本题:空队列 + pos 全部置 0)
    // for (i = l; i <= maxr; i++) { 推进状态; 回答 r == i 的询问; }
}

// ② 本题唯一需要维护的转移:撞点就截断队尾
if (pos[v] != 0) {                        // 队中已有 v
    int cut = pos[v];                     // 必须先保存!下面的循环会清掉 pos[v]
    for (int j = cut; j <= tail; j++) pos[que[j]] = 0;   // 连同 pos 一起"删"
    tail = cut - 1;                       // 队列截断到 cut - 1
} else {
    que[++tail] = v; pos[v] = tail;
}

// ③ 为什么队列长度 ≤ 13
//    规则规定:放入已存在的点数时,从那张牌到队尾全部取走,
//    于是"队中每种点数最多一张",而点数一共只有 13 种。

// ④ 状态很"窄"时,允许用"重放"代替"数据结构"
//    队里最多 13 张牌 ⟹ 每次操作 O(1) ⟹ 可以放心地多次从头模拟,
//    只要把"重放的次数"控制住(这里按左端点分组,最多 n 次)

// ⑤ 离线分组思想
//    "把所有询问按左端点归类,同一左端点共享一次前缀扫描",
//    和莫队、双指针是同一类套路

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
离线分组把询问按左端点 l 归类,同组共享一次扫描莫队、双指针、按端点分组的离线处理
pos 数组定位O(1) 找到某个点数在队中的位置需要"按值定位元素"的栈 / 队列 / 链表模拟
状态很窄就重放队长 ≤ 13,每步 O(1)状态空间小的模拟题、自动机式过程题
只扫必要的长度每组只扫到该组最大 r任何"离线 + 共享前缀"的优化
🌟
思考题:如果把点数范围改成 1 ≤ Aᵢ ≤ 10⁵(队列长度不再被 13 卡住),这套做法还能用吗?(提示:核心性质照样成立——队里永远不会有重复点数,撞点处理仍然是 O(1) 的截断 + 清 pos;变的只是 pos 不能再开成 14 大小的数组,换成 map 或哈希表即可,总体复杂度只多了个 log,思路完全不用改。)