同一个左端点只模拟一次;队列长度恒 ≤ 13,每放一张牌只要 O(1)。
小杨同学想用卡牌玩一种叫做"接竹竿"的游戏。
游戏规则是:每张牌上有一个点数 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 次询问的答案。
| 样例 | 内容 |
|---|---|
| 输入 #1 | 1 |
| 输出 #1 | 1 |
| 样例解释(第 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 按顺序往队尾放,一旦放下的点数在队里已经存在,就把"那一张"连同它后面所有的牌一起抽走。问最后队里剩几张牌。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] 内 |
v 如果已经在队里,就把"已有的那张 v"到队尾全部取走,其中当然包含新放的那张。取完之后队中不可能还有 v,所以每种点数在队中最多出现一次[0, 13],也保证了"放一张牌"的操作量是常数l,"放完 A_l … A_i 之后的队列"是一个唯一确定的状态,与后面还会放什么无关。所以同一个 l 的所有询问可以共用一次从头模拟,只要在扫到每个 r 时把当时的队长记下来pos[v] 记录点数 v 在队中的下标,pos[v] = 0 表示不在队里。撞点时把队尾截断到 pos[v] − 1,顺便把被删掉的那些牌的 pos 清 0;没有撞点就直接压入队尾。由于队列长度 ≤ 13,清 pos 也只要最多 13 步n 个;每个 l 只扫到"本组询问的最大 r",单组数据最坏 n(n + 1) / 2 ≈ 1.1 × 10⁸ 次操作,每次操作 O(1)(常数极小),C++ 实测可通过序列 A = 1 2 2 3 1 3(下标 1 ~ 6)。注意第 2 次询问题面已经给出了完整的队列变化序列,我们把它和另外三次一起摊开看。
第 2 次询问:l = 1, r = 6(从头放到尾)
| 步骤 | 放入 | 队中已有同点数吗 | 队列 | 队长 |
|---|---|---|---|---|
| 1 | A₁ = 1 | 没有 | {1} | 1 |
| 2 | A₂ = 2 | 没有 | {1, 2} | 2 |
| 3 | A₃ = 2 | 有(下标 2) | {1} | 1 |
| 4 | A₄ = 3 | 没有 | {1, 3} | 2 |
| 5 | A₅ = 1 | 有(下标 1) | { } | 0 |
| 6 | A₆ = 3 | 没有 | {3} | 1 |
只需要第 2 次询问的前 3 步
{1} → {1, 2} → {1}
第 3 步放 A₃ = 2 时撞上队中的 2(下标 2)
把下标 2 到队尾取走,只剩 {1}
✅ 答案 1
只需要第 2 次询问的前 5 步
{1} → {1, 2} → {1} → {1, 3} → { }
第 5 步放 A₅ = 1 时撞上队中的 1(下标 1)
从下标 1 到队尾全部取走,队列清空
✅ 答案 0
左端点变成 5,必须从 A₅ 重新开一局(不能沿用前面的队列)
放 A₅ = 1 → {1}(队里没有 1)
放 A₆ = 3 → 队里没有 3,直接入队 → {1, 3}
两张点数不同,谁也没撞上谁
✅ 答案 2
1 / 1 / 0 / 2,与样例输出完全一致。A₅ = 1 这张牌在 l = 1 的那一局里曾把整条队列清空,但在 l = 5 这一局里它只是"第一张牌"。| 时刻 | 队列 | 接下来放入 | 会发生什么 |
|---|---|---|---|
| 刚放完 1、2 | {1, 2} | 放入 2 | 队列变成 {1, 2, 2},出现重复 |
| 放入的瞬间 | {1, 2, 2} | 按规则取走"已有的 2 到队尾" | 变成 {1},重复立刻消失 |
设放入 v 之前,队中已经存在一张 v
规则要求把"已有的那张 v"到队尾全部取出(含两端)
取出后,队中既没有旧的 v,也没有新放的 v
所以任何时刻,每种点数在队中最多出现一次
点数一共只有 1…13 共十三种 ⟹ 队列长度恒 ≤ 13
推论:答案一定落在 [0, 13] 之内
✅ 队长 ≤ 13,这是"每次操作 O(1)"的基础
固定 l,依次放入 A_l, A_{l+1}, …
放完 A_l … A_i 之后的队列,只由 A_l … A_i 决定
与"后面还会放什么牌"完全无关
所以同一个 l 的所有询问可以共用这一次扫描
扫到 i = r 的那一刻把当前队长记下来即可
✅ 这是"按左端点分组"的正确性依据
同一组里 r 较小的询问,扫到它时就能立即回答
r 最大的那个询问决定了这次扫描要走多远
所以只扫到 maxr,剩下的位置本组再也用不到
不会漏答:每个询问的 r 都 ≤ maxr,
扫过它的那一刻答案已经记下
✅ 这是"只扫到 maxr"的正确性依据
pos 清 0,否则下次还会以为它们留在队里;l 的起始状态完全不同,必须按 l 各开一局;同一局里则按 r 从小到大边扫边答,扫到 maxr 才收工。把询问按 l 分组,同一个 l 只从空队开始扫一次,扫到各组最大 r 为止
l 的前缀会被反复扫描很多次;分组后每个 l 只扫一遍,而且只扫到"本组最远的 r",不会白扫后面用不到的位置。对每个 (l, r) 都从 A_l 开始放到 A_r,直接输出队长
| 方案 | 复杂度 | 结论 |
|---|---|---|
| 按左端点分组 + 增量模拟 | 单组 ≤ Σ(maxr − l + 1) ≈ 1.1 × 10⁸ | ✅ 推荐 |
| 每个询问独立重放 | 单组 ≤ q × n = 2.25 × 10⁸ | ⚠️ 能过但偏险 |
| 每个询问重放 + 每步线性找同点数 | 单组 ≤ q × n × n | ❌ 必然 TLE |
第一行 n;第二行 n 个点数(1 ~ 13);第三行 q;随后 q 行 l r。程序按左端点分组建模,展示队列的逐步变化与每次询问的答案。
点按钮开始 →
#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[];另外别忘了题意是包含两端一起取走。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 | 1 1 0 2 | 题面样例 1:四次询问四种情况 |
1 | 1 | 只有一张牌,队列长度 1 |
1 | 0 | 两张同点数,全部被取走 |
1 | 3 2 | 点数全不同:队列不会消,长度就是牌数 |
1 | 1 | 交替撞点:{1,2} 消掉后剩 {2} |
1 | 13 | 点数互不相同,队长达到上界 13 |
pos 了吗?③ 询问按 l 分组、按 r 排序了吗?④ 多测清空了吗?pos 里还留着"已经不在队里"的下标,下一次撞点会按错误位置截断,队列瞬间错乱。r 排序后边扫边答,不能扫到第一个询问的 r 就停下。1…13,pos 与队列数组都要留出余量(≥ 14)。T 最多 5 组,每组的 ask[]、ans[] 都要重置。n 个l 只扫 maxr − l + 1 个位置,其中 maxr 是该组询问里最大的 rl 都有询问且 maxr = n):n(n + 1) / 2 ≈ 1.1 × 10⁸(n = 1.5 × 10⁴)pos、至多 13 次清零、一次截断或入队,全是 O(1)A 数组 O(n);按左端点分组的询问 O(q);队列与 pos 各 14 个位置,因为"队中每种点数最多一张"保证了队长 ≤ 13。总空间只有几 MB。
✅ 单组最坏约 1.1 × 10⁸ 次"极轻量"操作(数组取值与自增),5 组数据合计约 5.6 × 10⁸ 次,常数极小,C++ 实测可通过;这正是本题标程采用的复杂度。关键是把 O(1) 的观察用满:队列短、pos 直接定位、同左端点共享扫描。
// ① 按左端点分组的通用骨架 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,思路完全不用改。)