「MXOI Round 2」队列

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

把每次插入的 1..x 压成一个块，只维护块前缀删除量；第 z 个元素和最大值都转成块级查询。

OJ: luogu

题目 ID: P9588

难度:普及+/提高

标签:数据结构模拟队列二分

日期: 2026-06-20 13:55

题意

维护一个队列，支持四种操作：

在队尾依次加入 1,2,...,x
弹出队头前 y 个元素
查询第 z 个元素
查询整个队列的最大值

需要对第 3、4 种操作输出答案。

思路

先看一个可以直接验证想法的朴素解：

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

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

    long long ignored_n;
    int q;
    cin >> ignored_n >> q;

    deque<i64> que;

    for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            for (int v = 1; v <= x; v++) {
                que.push_back(v);
            }
        } else if (op == 2) {
            int y;
            cin >> y;
            while (y--) que.pop_front();
        } else if (op == 3) {
            int z;
            cin >> z;
            cout << que[z - 1] << '\n';
        } else {
            i64 mx = 0;
            for (int j = 0; j < (int)que.size(); j++) {
                mx = max(mx, que[j]);
            }
            cout << mx << '\n';
        }
    }

    return 0;
}

本题最关键的是：每次插入的内容不是任意序列，而总是一个完整的连续块：

[1,2,3,...,x]

而删除操作又只会从整个队列前端删。

所以一个插入生成的块，后续只可能变成它自己的某个后缀：

[start+1, start+2, ..., len]

因此每个块只要维护两个量：

len：原始长度
start：已经被弹掉了多少前缀

这样四种操作都能在块层面完成：

插入：直接追加新块
弹出：从头块开始删，删完整块就跳过，否则只改 start
查询第 z 个元素：按块剩余长度前缀和定位到所在块，再换算块内排名
查询最大值：某个块的最大值永远是 len，遍历剩余块取最大即可

这种做法避免了展开 sum x 级别的真实元素。

代码

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#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXQ = 200000 + 5;

struct Block {
    i64 len;    // 原始长度 x
    i64 start;  // 当前已经弹掉了多少个前缀元素，剩下的是 [start+1 .. len]

    i64 size() const {
        return len - start;
    }

    i64 max_value() const {
        return len;
    }

    i64 kth(i64 k) const {
        return start + k;
    }
};

int q;
vector<Block> blocks;
int head_ptr = 0;
i64 prefix_size[MAXQ];

void rebuild_prefix() {
    i64 sum = 0;
    for (int i = head_ptr; i < (int)blocks.size(); i++) {
        sum += blocks[i].size();
        prefix_size[i] = sum;
    }
}

int find_block_by_rank(i64 z) {
    int left = head_ptr;
    int right = (int)blocks.size() - 1;
    int ans = right;

    while (left <= right) {
        int mid = (left + right) >> 1;
        if (prefix_size[mid] >= z) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

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

    long long ignored_n;
    cin >> ignored_n >> q;

    for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;

        if (op == 1) {
            i64 x;
            cin >> x;
            blocks.push_back({x, 0});
        } else if (op == 2) {
            i64 y;
            cin >> y;

            while (y > 0) {
                i64 cur_size = blocks[head_ptr].size();
                if (cur_size <= y) {
                    y -= cur_size;
                    head_ptr++;
                } else {
                    blocks[head_ptr].start += y;
                    y = 0;
                }
            }
        } else if (op == 3) {
            i64 z;
            cin >> z;

            rebuild_prefix();
            int idx = find_block_by_rank(z);
            i64 prev = (idx == head_ptr ? 0 : prefix_size[idx - 1]);
            i64 inside_rank = z - prev;
            cout << blocks[idx].kth(inside_rank) << '\n';
        } else {
            i64 answer = 0;
            for (int j = head_ptr; j < (int)blocks.size(); j++) {
                if (blocks[j].size() > 0) {
                    answer = max(answer, blocks[j].max_value());
                }
            }
            cout << answer << '\n';
        }
    }

    return 0;
}

复杂度

块数最多等于插入次数，所以不超过 q。

当前实现中：

插入、弹出均摊 $O(1)$
查询第 z 个元素、查询最大值为 $O(块数)$

总体空间复杂度 $O(q)$ 。

总结

这题的核心不是维护普通队列，而是先识别出：

队列始终由若干个 1..x 的块拼接而成

一旦把它压缩成块结构，所有操作都会自然很多。

P9588 「MXOI Round 2」队列

题目描述

小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下：

$1\ x$ ：这是第一种操作，表示从队尾依次插入 $1,2,3,\cdots,x$ ；

$2\ y$ ：这是第二种操作，表示弹出队头的前 $y$ 个元素；

$3\ z$ ：这是第三种操作，表示查询队列中的第 $z$ 个元素；

$4$ ：这是第四种操作，表示查询队列中所有元素的最大值。

你需要帮助他维护这个队列，并对于每个第三种操作和第四种操作，输出查询的答案。

输入格式

第一行两个整数 $c,q$ ，其中 $c$ 表示测试点编号。 $c=0$ 表示该测试点为样例。

接下来 $q$ 行，每行 $1 \sim 2$ 个整数，表示一个操作，格式见【题目描述】。

输出格式

对于每个第三种操作和第四种操作，输出一行一个整数，表示查询的答案。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例解释 #1】

在进行第四次操作后，队列中的元素依次为 $3,4,5,1,2,3,1,2,3,4$ 。

在进行第七次操作后，队列中的元素依次为 $2,3,1,2,3,4$ 。

【样例 #2】

见附加文件中的 queue/queue2.in 与 queue/queue2.ans。

该样例满足测试点 $1$ 的限制。

【样例 #3】

见附加文件中的 queue/queue3.in 与 queue/queue3.ans。

该样例满足测试点 $4$ 的限制。

【样例 #4】

见附加文件中的 queue/queue4.in 与 queue/queue4.ans。

该样例满足测试点 $11$ 的限制。

【样例 #5】

见附加文件中的 queue/queue5.in 与 queue/queue5.ans。

该样例满足测试点 $15$ 的限制。

【样例 #6】

见附加文件中的 queue/queue6.in 与 queue/queue6.ans。

该样例满足测试点 $20$ 的限制。

【数据范围】

设 $\sum x$ 表示单个测试点内 $x$ 之和。

对于 $100\%$ 的数据， $1 \le q \le 2\times 10^5$ ， $1 \le x,y,z \le 10^9$ ， $0 \le \sum x \le 2\times10^{14}$ ，保证在进行第二种操作前队列内元素个数不小于 $y$ ，在进行第三种操作前队列内元素个数不小于 $z$ ，在进行第四种操作前队列内元素个数大于 $0$ 。

测试点编号	$q \le$	$x \le$	$\sum x \le$	特殊性质
$1\sim3$	$500$	$500$	$2\times10^5$	C
$4\sim8$	$5000$	$5000$	$2\times10^7$	无
$9\sim10$	$2\times10^5$	$10^9$	$2\times10^{14}$	AB
$11\sim12$	$2\times10^5$	$10^9$	$2\times10^{14}$	B
$13\sim14$	$2\times10^5$	$10^9$	$2\times10^9$	AC
$15\sim16$	$2\times10^5$	$10^9$	$2\times10^9$	C
$17\sim18$	$2\times10^5$	$500$	$2\times10^7$	无
$19$	$2\times10^5$	$10^9$	$2\times10^9$	无
$20$	$2\times10^5$	$10^9$	$2\times10^{14}$	无

特殊性质 A：没有第二种操作。

特殊性质 B：没有第三种操作。

特殊性质 C：没有第四种操作。

「MXOI Round 2」队列

目录

题意

思路

代码

复杂度

总结