[集训队互测 2018] 完美的队列

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

把每个操作的值看成一段存活区间，先分块双指针求出每个操作被弹出的时刻，再在时间轴上扫描统计颜色数。

OJ: luogu

题目 ID: P9247

难度:省选/NOI-

标签:分块双指针扫描线数据结构

创建: 2026-10-02 15:07

更新: 2026-10-03 12:11

形式化题目

有 $n$ 个队列，第 $i$ 个队列有一个容量上界 $a_i$ 。

依次执行 $m$ 次操作，第 $t$ 次操作为「对编号在 $[l_t,r_t]$ 内的每个队列压入一个权值 $x_t$ ，然后若某队列的元素个数大于 $a_i$ ，则反复弹出队首元素直到个数不超过 $a_i$ 」。

因为队列只在队尾压入、只从队首弹出，所以每个队列在任何时刻保留的都是它最近被压入的 $a_i$ 个元素，更早的元素一定已经被弹掉。

要求：在每次操作结束后，统计此刻所有队列中出现过的不同权值的个数。

暴力解法

思路

按题意直接模拟即可：为每个队列开一个双端队列，操作时对 $[l,r]$ 内的每个队列压入 $x_t$ ，并不断弹出队首直到长度不超过 $a_i$ 。每次操作结束后，把所有队列里的元素丢进一个集合，集合大小就是答案。

这份代码的作用是确认题意的细节（尤其是「弹出发生在压入之后」以及「统计的是全局不同权值」），并作为对拍的标准答案。

代码

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/**
 * 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-02 15:07
 * update_at: 2026-10-02 15:07
 */
// brute.cpp：最朴素的模拟。每个队列用一个 deque 维护，队尾 push、队首 pop，
// 每次操作结束后扫一遍所有队列统计不同权值种数。小数据对拍用。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200005;

int n, m;
int a[maxn];
deque<int> q[maxn];

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

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

    for (int t = 1; t <= m; t++) {
        int l, r, x;
        cin >> l >> r >> x;

        // 对区间内每个队列执行 push，并一直 pop 直到 size <= a_i
        for (int i = l; i <= r; i++) {
            q[i].push_back(x);
            while ((int)q[i].size() > a[i]) q[i].pop_front();
        }

        // 统计当前所有队列里出现过的不同权值个数
        set<int> kinds;
        for (int i = 1; i <= n; i++) {
            for (size_t k = 0; k < q[i].size(); k++) kinds.insert(q[i][k]);
        }
        cout << kinds.size() << "\n";
    }

    return 0;
}

复杂度

单次操作需要遍历 $[l,r]$ 中的每个队列，并在最后扫描全部元素，最坏为 $O(n)$ ，总复杂度 $O(nm)$ 。在 $n,m\le 10^5$ 时无法接受。

瓶颈

暴力的浪费在于它反复重算同一件事。

注意队列「只保留最后 $a_i$ 个元素」这个性质是与元素的权值无关的：第 $i$ 个队列里保留哪些元素，只取决于历史上哪些操作覆盖了它。所以要判断第 $t$ 次操作压入的 $x_t$ 在某一时刻是否还在队列里，只需要知道「从第 $t$ 次操作之后算起，第 $i$ 个队列又接收了多少次操作」——一旦又接收了 $a_i$ 次， $x_t$ 就被挤出去了。

于是答案与「每个操作压入的值的存活时间」直接挂钩，而这件事可以脱离权值单独计算。暴力对我们唯一有用的信息就是它验证了这个等价性。

正解

思路

第一步：把「权值种类数」转换成「区间的并」问题。

固定一个队列 $i$ 。设覆盖 $i$ 的操作时刻依次为 $p_1<p_2<\cdots$ 。第 $i$ 个队列保留最后 $a_i$ 个元素，因此 $p_j$ 压入的元素在时刻 $t$ （ $t\ge p_j$ ）还活着，等价于 $p_j,p_{j+1},\dots$ 中落在 $[p_j,t]$ 内的个数不超过 $a_i$ 。

反过来想：对每个操作 $j$ ，定义

last[j]=\max_{i\in[l_j,r_j]} f_i(j),\qquad f_i(j)=\text{第 } i \text{ 个队列里把 } x_j \text{ 挤出去的最早时刻}

其中若从 $j$ 之后覆盖 $i$ 的操作不足 $a_i$ 次，就规定 $f_i(j)=m+1$ （人为规定第 $m+1$ 时刻清空所有队列）。

那么 $x_j$ 的存活区间恰好是 $[j,\,last[j]-1]$ ：只要有一个队列先把它弹掉，它就已经不在全局里了；而所有队列都还留着它的那些时刻，它都在。于是原问题变成：

给定 $m$ 个值 $x_1,\dots,x_m$ 和各自的存活区间 $[j,last[j]-1]$ ，求每个时刻 $t$ 的「出现过的不同值个数」。

这个问题在时间轴上扫一遍、开一个桶 cnt[x] 即可：时刻 $t$ 加入 $x_t$ ，并在时刻 $last[j]$ 删除 $x_j$ ；只要某个值的计数从 $0$ 变成 $1$ （或从 $1$ 变成 $0$ ）答案就 $\pm1$ 。复杂度 $O(m)$ 。

第二步： $last[j]$ 的单调性。

把 $j$ 增大， $f_i(j)$ 不会减小——因为后面的操作 $j$ 前面多了更多元素，要弹出它需要等更久。所以对于固定的 $i$ ， $f_i(j)$ 关于 $j$ 单调。而 $last[j]$ 是一段区间上的 $\max$ ，直接对每个 $j$ 单独求会太慢。

第三步：分块求 $f$ 。

把 $1..n$ 按块长 $B=\lfloor\sqrt n\rfloor$ 分块，逐块计算该块能贡献的 $last$ 。对固定块 $[L,R]$ ，按操作与块的位置关系分三类：

无交：直接忽略；
整块： $l_t\le L$ 且 $R\le r_t$ ，它对块内每个位置的贡献完全相同，只加一个整体标记；
散块：与块有交但不完全覆盖，它对块内位置的影响是「一部分加、一部分不加」。

整块影响。 对整块操作维护一个整体标记 $add$ （块内每个位置都多了 $add$ 个元素），同时维护 $mx=\max_i\big(a_i-\text{该位置的散块贡献}\big)$ ，即块内「最紧」的位置还剩多少余量。 $mx\ge add$ 表示块内所有位置都还装得下，可以继续加入操作；一旦 $mx<add$ 就说明有位置被撑爆。

于是对 $l=1..m$ 做双指针： $r$ 只增不减，不断把操作 $r+1$ 加进来直到被撑爆，此时 $r$ 就是第 $l$ 个操作对应的弹出时刻（对块内的紧位置而言），若整块操作 $l$ 存在就更新 $last[l]$ ，然后把操作 $l$ 删掉。加入 / 删除一个整块操作只需 $add\pm1$ ；加入 / 删除一个散块操作需要 $O(B)$ 暴力修改块内位置并重算 $mx$ 。每个操作在整块影响里总消耗 $O(B)$ ，总共 $O\big(mB + (m/B)\cdot m\big)$ ——这里第二项是每块 $O(m)$ 的双指针开销。

散块影响。 散块操作的弹出时刻需要在单点上精确计算，逐点做。

对当前块，把所有相关操作按时间取出来存成 allOp[1..siz]，并在末尾放哨兵 allOp[siz+1] = m+1。用前缀和 prefixFull 记下「前 $s$ 个相关操作中有多少个整块操作」，并把散块操作的下标记在 scatterPos 里。

对块内每个点 $i$ 单独跑双指针：窗口 $[l,r]$ （ $l,r$ 是散块操作下标）内维护 maxAdd = 窗口覆盖 $i$ 的操作个数（含中间的整块操作，由前缀和一次性算出）。当 maxAdd > a_i 时，说明 $x_{allOp[scatterPos[l]]}$ 被抓出来了。

设当前还装得下，还差 need = a_i - maxAdd + 1 次覆盖才会撑爆。窗口右端之后的一段位置上，接下来的操作要么全是整块操作、要么已经没有操作了——所以只要往后跳 need 个「相关位置」即可，跳到的位置正是弹出时刻。这一步用 allOp[scatterPos[r] + need] 直接算出， $O(1)$ 。

两个细节需要注意：

如果加入某个散块操作后立刻 maxAdd > a_i（“恰好不满足”），先把右端点回退一格，算完 last 再补回来，保证和上面「还装得下」的情形走同一条公式。
第 $l$ 个散块操作删除时，要连同它到下一个散块之间的整块操作一起从 maxAdd 中减掉，即 prefixFull[scatterPos[l+1]] - prefixFull[scatterPos[l]]。

每个散块点跑一次 $O(\text{散块个数})$ 的双指针，单块 $O(B\cdot m)$ … 但由于每个操作最多只对「 $l_t$ 所在的块」和「 $r_t$ 所在的块」是散块，所以 $\sum_{\text{块}}|\text{散块}| = O(m)$ ，散块影响总复杂度也是 $O(mB)$ 。

把两部分合起来，总复杂度为 $O\big((n+m)\sqrt n\big)$ ，常数稍大但完全可以通过。

代码

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204/**
 * 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-02 15:07
 * update_at: 2026-10-02 15:07
 *
 * P9247 [集训队互测 2018] 完美的队列
 *
 * 关键转化：
 *   1. 队列 i 永远只保留"最后 a_i 个压进它的操作"，所以操作 j 压入的值 x_j
 *      在所有覆盖 j 的队列里都还活着，当且仅当 j 之后覆盖该队列的操作数 < a_i。
 *   2. 定义 last[j] = max_{i in [l_j, r_j]}（使第 i 个队列里 x_j 被弹出的最早时刻），
 *      则 x_j 的存活区间就是 [j, last[j] - 1]（last[j] = m+1 表示活到最后）。
 *   3. 最后一遍时间轴扫描 + 桶：在 t 时刻加入 x_t，在 last[j] 时刻删除 x_j，
 *      维护"出现过几次的值种类数"即可。
 *
 * 计算 last 用分块（块长 sqrt(n)）：
 *   对每个块，把所有与它有交的操作按时间排成一列，
 *   整块操作（完全覆盖块）走"整体加法 + 块内最大剩余容量"的双指针；
 *   散块操作走"逐点双指针"，并用前缀和把中间整块操作一次性算出来。
 *   每个操作至多对两个块是散块，总复杂度 O((n + m) sqrt(n))。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

int n, m;
int a[maxn];                 // 每个队列的容量
int ql[maxn], qr[maxn], qx[maxn]; // 每次操作的 l, r, x

int blockSize, blockCnt;     // 块长、块数
int blkL[maxn], blkR[maxn];  // 每个块的左右端点

// ---------- 整块影响（整块操作整体打标记，散块操作暴力重算） ----------
int curL, curR;              // 当前正在处理的块
int capTmp[maxn];            // capTmp[i] = a_i 减去块内散块操作对 i 的贡献
int gMx;                     // max_i capTmp[i]
int gAdd;                    // 整块操作的个数（整体加标记），即整块操作对每个位置的贡献

// ---------- 散块影响（逐点双指针 + 前缀和） ----------
int allOp[maxn];             // 当前块所有相关操作的时刻，末尾放哨兵 m+1
int prefixFull[maxn];        // 前缀和：相关操作中整块操作的个数
int scatterPos[maxn];        // 散块操作在 allOp 中的下标
int siz;                     // 相关操作个数
int pointIdx;                // 散块操作个数
int gMaxAdd;                 // 单点当前窗口里覆盖它的操作个数（含整块操作的贡献）

int lastOp[maxn];            // 操作 j 的存活右端点（不含），初始 0

// ---------- 扫描线 ----------
int cntVal[maxn];            // 每个值当前被多少个队列持有
vector<int> dieAt[maxn];     // dieAt[t] = 在 t 时刻死亡的操作编号

int maxInt(int x, int y) { return x > y ? x : y; }

// 把第 curr 个操作加入（val = 1）或移出（val = -1）整块影响的状态。
// 整块操作只动整体标记；散块操作需要在块内逐点暴力修改并重算最大值。
void applyOpt(int curr, int val) {
    int l = ql[curr], r = qr[curr];
    if (l > curR || r < curL) return;              // 与本块无交，直接忽略
    if (l <= curL && curR <= r) { gAdd += val; return; } // 整块操作
    gMx = 0;                                       // 散块操作：块内暴力重算
    for (int i = curL; i <= curR; i++) {
        if (l <= i && i <= r) capTmp[i] -= val;
        if (capTmp[i] > gMx) gMx = capTmp[i];
    }
}

// 整块影响：双指针求所有整块操作对应的 last。
// gMx >= gAdd 说明块内每个位置的元素个数都没超过容量，可以继续往后加操作。
void solveWholeBlock() {
    gMx = 0;
    for (int i = curL; i <= curR; i++) {
        capTmp[i] = a[i];
        if (capTmp[i] > gMx) gMx = capTmp[i];
    }
    gAdd = 0;
    int r = 0;
    for (int l = 1; l <= m; l++) {
        while (r < m && gMx >= gAdd) { // 不断加入，直到某个位置被撑爆
            r++;
            applyOpt(r, 1);
        }
        if (r == m && gMx >= gAdd) r = m + 1; // 一直没爆，视为第 m+1 时刻清空
        // 只有整块操作才由整块影响定 last，散块操作的 last 交给下面逐点处理
        if (ql[l] <= curL && curR <= qr[l]) lastOp[l] = maxInt(lastOp[l], r);
        applyOpt(l, -1); // 左端点右移，去掉第 l 个操作
    }
}

// 散块影响：把第 q 个散块操作加入当前单点窗口。
// isFirst 表示窗口本来为空（此时要把 [上一个散块, 当前散块) 之间的整块操作一次算进来）。
void updatePart(int i, int q, int isFirst, int val) {
    int idx = allOp[scatterPos[q]];
    if (!isFirst) gMaxAdd += (prefixFull[scatterPos[q]] - prefixFull[scatterPos[q - 1]]) * val;
    if (ql[idx] <= i && i <= qr[idx]) gMaxAdd += val;
}

// 左端点右移：删掉第 l 个散块操作（以及它到下一个散块之间的整块操作）。
void delPart(int i, int l) {
    int idx = allOp[scatterPos[l]];
    if (l < pointIdx) gMaxAdd -= prefixFull[scatterPos[l + 1]] - prefixFull[scatterPos[l]];
    if (ql[idx] <= i && i <= qr[idx]) gMaxAdd -= 1;
}

// 散块影响：块内每个点单独跑一次双指针。
// 一个点只关心自己这个队列，所以 mx = a_i 固定；
// 窗口里"覆盖该点"的操作个数 gMaxAdd 一旦超过 a_i 就会弹掉队首。
void solveScatter() {
    siz = 0;
    pointIdx = 0;
    prefixFull[0] = 0;
    for (int t = 1; t <= m; t++) {
        if (ql[t] > curR || qr[t] < curL) continue; // 与本块无交
        siz++;
        allOp[siz] = t;
        if (ql[t] <= curL && curR <= qr[t]) {
            prefixFull[siz] = prefixFull[siz - 1] + 1; // 整块操作
        } else {
            prefixFull[siz] = prefixFull[siz - 1];
            scatterPos[++pointIdx] = siz;             // 记下散块操作的位置
        }
    }
    allOp[siz + 1] = m + 1; // 哨兵

    for (int i = curL; i <= curR; i++) {
        int mx = a[i];
        gMaxAdd = 0;
        int r = 0;
        for (int l = 1; l <= pointIdx; l++) {
            while (r < pointIdx && mx >= gMaxAdd) { // 还能塞，继续加散块操作
                r++;
                updatePart(i, r, l == r, 1);
            }
            int idx = allOp[scatterPos[l]];
            if (ql[idx] <= i && i <= qr[idx]) { // 这个散块操作真的覆盖点 i
                if (mx < gMaxAdd) {             // 回溯一格，回到"恰好还装得下"
                    updatePart(i, r, l == r, -1);
                    r--;
                    int need = mx - gMaxAdd + 1; // 还差几次覆盖才撑爆
                    int t = scatterPos[r] + need;
                    if (t > siz + 1) t = siz + 1; // 后面不够了就活到清空时刻
                    lastOp[idx] = maxInt(lastOp[idx], allOp[t]);
                    r++;
                    updatePart(i, r, l == r, 1);
                } else {
                    int need = mx - gMaxAdd + 1;
                    int t = scatterPos[r] + need;
                    if (t > siz + 1) t = siz + 1;
                    lastOp[idx] = maxInt(lastOp[idx], allOp[t]);
                }
            }
            delPart(i, l);
        }
    }
}

void read_data() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int t = 1; t <= m; t++) cin >> ql[t] >> qr[t] >> qx[t];
}

void solve() {
    blockSize = (int)sqrt((double)n);
    if (blockSize < 1) blockSize = 1;
    blockCnt = (n + blockSize - 1) / blockSize;
    for (int b = 1; b <= blockCnt; b++) {
        blkL[b] = (b - 1) * blockSize + 1;
        blkR[b] = b * blockSize;
        if (blkR[b] > n) blkR[b] = n;
    }

    for (int b = 1; b <= blockCnt; b++) {
        curL = blkL[b];
        curR = blkR[b];
        solveWholeBlock(); // 整块操作决定的 last
        solveScatter();    // 散块操作决定的 last
    }

    // 时间轴扫描：x_j 存活区间 [j, lastOp[j] - 1]
    for (int j = 1; j <= m; j++) dieAt[lastOp[j]].push_back(j);

    int res = 0;
    for (int t = 1; t <= m; t++) {
        if (++cntVal[qx[t]] == 1) res++;          // 加入第 t 次操作的值
        for (size_t k = 0; k < dieAt[t].size(); k++) {
            int j = dieAt[t][k];
            if (--cntVal[qx[j]] == 0) res--;      // 删除在 t 时刻死掉的值
        }
        cout << res << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    read_data();
    solve();
    return 0;
}

复杂度

分块后每个块对整块影响做一次 $O(m)$ 的双指针、对散块逐个做 $O(\text{散块数})$ 的双指针；散块总数是 $O(m)$ ，于是预处理 $last$ 为 $O\big((n+m)\sqrt n\big)$ ，最后时间轴扫描为 $O(m)$ 。总时间复杂度 $O\big((n+m)\sqrt n\big)$ ，空间复杂度 $O(n+m)$ 。

总结

这道题的难点不在数据结构，而在转化的层次：

队列按容量 $a_i$ 保留最后 $a_i$ 个元素，因此「元素是否还在」与权值无关，只与「之后又来了多少覆盖它的操作」有关。
每个操作的值 $x_j$ 在所有覆盖它的队列里都活着时才可见，所以它的存活区间由 $\max_i f_i(j)$ 决定。这样就把「统计不同权值」变成了「区间并覆盖的统计」。
$f_i(j)$ 关于 $j$ 单调，使得双指针可行；而「区间取 $\max$ 」不能逐点做，于是把它拆成整块影响与散块影响两部分。
整块影响利用「整体加法 + 块内最大余量」把双指针压到 $O(1)$ 摊还；散块影响利用「跳过中间整块只需 $O(1)$ 」的观察，把每个点的双指针也压到与散块数同阶。

有了每个操作的存活区间，最后只需要一遍 $O(m)$ 的桶扫描线。整道题的关键是把「队列模拟」换成「区间端点 + 计数」，剩下的分块只是为了在 $10^5$ 规模下求出这些端点。

P9247 [集训队互测 2018] 完美的队列

题目描述

小 D 有 $n$ 个 std::queue<int>，他把它们编号为 $1$ 到 $n$ 。

小 D 对每个队列有不同的喜爱程度，如果有他不怎么喜欢的队列占用了太大的内存，小 D 就会不开心。

具体地说，如果第 $i$ 个队列的 size() 大于 $a_i$ ，小 D 就会对这个队列一直执行 pop() 直到其 size() 小等于 $a_i$ 。

现在这些队列都是空的，小 D 觉得太单调了，于是他决定做一些操作。

每次操作都可以用 l r x 来描述，表示对编号在 $[l,r]$ 内的所有队列执行 push(x) 操作。当然，每次操作结束后，小 D 都会用之前提到的方法来避免这些队列占用太大的内存。

小 D 的队列很神奇，所以他能用 $O(1)$ 的时间执行每次操作。

相信大家的队列都能做到，于是小 D 把这道题出给大家送分。

为了证明你确实执行了这些操作，你需要在每次操作后输出目前还在队列内的权值种数。

输入格式

第一行两个正整数 $n,m$ ，分别表示队列个数和操作个数。

第二行 $n$ 个正整数，第 $i$ 个表示 $a_i$ 。

接下来 $m$ 行，每行三个正整数 l r x，其中第 $i$ 行表示第 $i$ 次操作。

输出格式

输出共 $m$ 行，每行一个非负整数，表示第 $i$ 次操作结束后所有队列中的权值种数。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

样例解释

第一次操作后，队列变成 $\{1\}\{1\}\{\}$ ，还在队列内的权值有 $1$ ，共 $1$ 种。

第二次操作后，队列变成 $\{1\}\{1,2\}\{2\}$ ，还在队列内的权值 $1,2$ ，共 $2$ 种。

第三次操作后，队列变成 $\{3\}\{2,3\}\{2,3\}$ ，还在队列内的权值有 $2,3$ ，共 $2$ 种。

数据范围

对于所有数据， $n,m,a_i,x\leq 10^5$ ， $l\leq r$ 。

共 $20$ 个测试点，每个测试点 $5$ 分，其中第 $k$ 个测试点满足 $n,m,a_i,x\leq 5000k$ 。

特别地，以下几个测试点满足一些特殊性质：

测试点 $5$ ： $a_i=1$ ；
测试点 $7$ ： $a_i=2$ ；
测试点 $9$ ： $a_i=10$ ；
测试点 $11$ ： $a_i\leq 10$ ；
测试点 $13,15$ ： $\sum a_i\leq 10^6$ 。

对于每个测试点，你需要通过满足该点数据范围及性质的所有数据才能获得该点的分数。

[集训队互测 2018] 完美的队列

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结