[Algo Beat Contest 017 B] 线性筛
比较分段模拟和树状数组三种维护当前序列的方法，正式主解用树状数组 kth 定位动态排名。
OJ: luogu
题目 ID: P17233
难度:普及
标签:树状数组模拟数据结构
日期: 2026-08-11 07:37
形式化题目
给定一个序列。每轮在当前剩余序列中，同时删除所有排名为完全立方数的位置，剩余元素保持原相对顺序并重新编号。不断重复直到序列为空，要求输出轮数以及每轮被删除的元素值。
暴力
最直接的做法是维护当前剩余序列，每轮扫描当前位置是否为完全立方数。如果当前位置是
这个暴力完整体现了“同时删除”的语义：本轮所有位置都按本轮开始时的当前序列编号判断，没被删除的元素按原相对顺序进入下一轮。它适合理解题意和作为对拍基准，不作为正式主解。
cpp
/**
* 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-08-11 07:37
* update_at: 2026-08-11 11:18
*/
// brute.cpp：小数据暴力解，直接维护当前剩余序列并逐轮扫描。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n;
int is_cube[MAXN]; // is_cube[i] 表示 i 是否为完全立方数
void init_cube() {
// 预处理完全立方数位置，之后每轮扫描时 O(1) 判断当前位置是否要删除。
for (int i = 1; 1LL * i * i * i < MAXN; i++) {
is_cube[i * i * i] = 1;
}
}
int count_deleted(int len) {
// 当前长度为 len 时，本轮会删除 1^3, 2^3, ... 这些排名。
int cnt = 0;
for (int i = 1; 1LL * i * i * i <= len; i++) cnt++;
return cnt;
}
int count_rounds(int len) {
// 题目要求先输出总轮数。这里只模拟长度变化，不关心具体元素。
int rounds = 0;
while (len > 0) {
len -= count_deleted(len);
rounds++;
}
return rounds;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init_cube();
cin >> n;
vector<int> cur(n);
for (int i = 0; i < n; i++) cin >> cur[i];
cout << count_rounds(n) << '\n';
// cur 表示本轮开始时的当前序列，next_cur 表示删完本轮后的剩余序列。
vector<int> next_cur;
while (!cur.empty()) {
next_cur.clear();
bool first_output = true;
for (int i = 0; i < (int)cur.size(); i++) {
int pos = i + 1;
if (is_cube[pos]) {
// 删除位置全部按本轮开始时的 cur 下标判断，符合“同时删除”。
if (!first_output) cout << ' ';
cout << cur[i];
first_output = false;
}
else {
// 没被删除的元素按原相对顺序进入下一轮。
next_cur.push_back(cur[i]);
}
}
cout << '\n';
// 滚动数组：下一轮继续处理剩余序列。
cur.swap(next_cur);
}
return 0;
}思路
这一题有三种实现路线。下面按代码理解难度从低到高介绍：
- 解法一：双队列流式重建连续段。它最接近暴力模拟，只是把当前序列压缩成若干原数组连续段。
- 解法二：链表维护连续段。它原地维护这些连续段，展示当前序列被不断切开的过程。
- 解法三：树状数组维护动态排名。它是正式主解，对应
main.cpp，复杂度证明最稳定。
三种解法都在解决同一个核心问题：删除依据是“当前排名”，而输出元素来自“原数组下标”。所以我们需要维护一种结构，把当前第
解法一：双队列流式重建连续段
思路
暴力每轮直接保存整个当前序列。双队列分段写法保留这个“每轮生成下一轮”的直觉，但不逐个元素维护，而是把当前序列压成若干连续段。
一个段 Segment{pos,start,len} 表示：当前序列中从排名 pos 开始的 len 个元素，正好对应原数组中从 start 开始的连续 len 个元素。
每轮用 q1 保存旧段，q2 保存删除后产生的新段。先生成本轮所有完全立方排名，然后从左到右扫描 q1。如果某个立方排名落在当前段内，就输出对应原数组元素；两个删除点之间没被删的部分，作为新段推入 q2。本轮结束后交换两个队列。
这种写法天然保证同时删除：本轮定位只看 q1 中的旧段，新生成的段只进入 q2，不会影响本轮后续排名。
代码
cpp
/**
* 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-08-11 10:33
* update_at: 2026-08-12 15:02
*/
// main-queue.cpp：另一种分段模拟，用两个队列维护当前剩余序列的连续原数组段。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
struct Segment {
int pos; // 这一段在当前序列中的起始排名
int start; // 这一段在原数组中的起始下标
int len; // 这一段连续长度
};
int n;
int a[MAXN];
queue<Segment> q1, q2; // q1 本轮开始时的旧段，q2 本轮生成的新段（本轮的删除只看 q1）
int cube_pos[105]; // 本轮所有完全立方排名 1, 8, 27, ...，递增
int cube_cnt;
vector<vector<int> > rounds;
// 生成长度为 len 时的全部完全立方排名。
void build_cube_positions(int len) {
cube_cnt = 0;
for (long long x = 1; x * x * x <= len; x++) {
cube_cnt++;
cube_pos[cube_cnt] = (int)(x * x * x);
}
}
// 把一个保留段推入新队列 q2。
void push_segment(int pos, int start, int len) {
if (len <= 0) return;
Segment seg;
seg.pos = pos;
seg.start = start;
seg.len = len;
q2.push(seg);
}
// 读入原数组。
void read_input() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
}
// 处理一轮：扫描 q1 中的旧段，收集本轮删除的元素值，并把保留段生成到 q2。
// new_len 通过引用带回本轮保留的元素总数。
vector<int> process_one_round(int len, int &new_len) {
build_cube_positions(len);
vector<int> deleted_values;
// ptr 指向下一个要处理的立方排名；new_len 统计本轮保留的元素总数。
int ptr = 1;
new_len = 0;
while (!q1.empty()) {
Segment seg = q1.front();
q1.pop();
int seg_l = seg.pos;
int seg_r = seg.pos + seg.len - 1;
// 跳过段之前已经处理完的立方排名。
while (ptr <= cube_cnt && cube_pos[ptr] < seg_l) ptr++;
int last_offset = 0; // 已经处理到段内 0-based 的 last_offset 之前
while (ptr <= cube_cnt && cube_pos[ptr] <= seg_r) {
int offset = cube_pos[ptr] - seg.pos; // 0-based 段内偏移
deleted_values.push_back(a[seg.start + offset]);
// 该删除点之前没被删的部分作为保留段，进入下一轮。
int keep_len = offset - last_offset;
if (keep_len > 0) {
push_segment(new_len + 1, seg.start + last_offset, keep_len);
new_len += keep_len;
}
last_offset = offset + 1;
ptr++;
}
// 段尾剩余部分保留。
int tail_len = seg.len - last_offset;
if (tail_len > 0) {
push_segment(new_len + 1, seg.start + last_offset, tail_len);
new_len += tail_len;
}
}
return deleted_values;
}
// 逐轮删除，直到序列为空，把每轮删除的元素值存进 rounds。
void solve() {
// 初始整个序列是一个段：排名从 1 开始，对应原数组 [1, n]。
Segment first;
first.pos = 1;
first.start = 1;
first.len = n;
q1.push(first);
int len = n; // 当前剩余序列长度
while (len > 0) {
int new_len = 0;
rounds.push_back(process_one_round(len, new_len));
swap(q1, q2); // 下一轮处理本轮生成的保留段
len = new_len;
}
}
// 输出轮数与每轮删除的元素。
void print_answers() {
cout << rounds.size() << '\n';
for (int i = 0; i < (int)rounds.size(); i++) {
for (int j = 0; j < (int)rounds[i].size(); j++) {
if (j) cout << ' ';
cout << rounds[i][j];
}
cout << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
print_answers();
return 0;
}复杂度
时间复杂度与每轮段数总扫描量有关。它的代码直观，实测可以通过大数据压力测试，但严格最坏界不如树状数组清晰。
空间复杂度为
解法二：链表维护连续段
思路
链表分段写法同样维护当前序列由哪些原数组连续段拼接而成，但它不是每轮整体生成一个新队列，而是在段链表上记录本轮要删除的位置，再统一把受影响的段切开。
每个链表节点记录一个连续段的原数组起点和长度。因为本轮的完全立方排名递增，所以可以用指针从前往后定位所有待删位置。定位阶段只记录“删哪个节点、节点内偏移是多少”，不能立刻修改链表。等本轮全部定位完成后，再按这些偏移把对应段切成若干新段。
这比双队列写法更贴近“当前序列在原地维护”的想法，但细节也更多，尤其要处理同一轮多个删除点落在同一个段内的情况。
代码
cpp
/**
* 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-08-11 10:18
* update_at: 2026-08-12 14:07
*/
// main-link.cpp：另一种解法，用链表维护当前剩余序列的连续原数组段。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n;
int a[MAXN];
// 每个节点表示当前序列中的一个连续段：a[start_pos] ... a[start_pos + len - 1]
int start_pos[MAXN * 3]; // 段在原数组中的起始下标
int seg_len[MAXN * 3]; // 段长度
int nxt[MAXN * 3]; // 段链表：后继节点
int pre[MAXN * 3]; // 段链表：前驱节点
int node_cnt; // 已分配的节点数
int head_node; // 段链表头节点
// 本轮要删除的位置记录：第 i 个删除点落在 deleted_node[i] 段内，偏移为 deleted_offset[i]。
int deleted_node[MAXN];
int deleted_offset[MAXN]; // 段内 1-based 偏移，表示该位置在段内的第几个元素
int deleted_value[MAXN];
int delete_cnt;
vector<vector<int> > rounds;
// 新建一个连续段节点：原数组从 pos 开始、长度为 len；len <= 0 返回空节点。
int new_node(int pos, int len) {
if (len <= 0) return 0;
node_cnt++;
start_pos[node_cnt] = pos;
seg_len[node_cnt] = len;
nxt[node_cnt] = 0;
pre[node_cnt] = 0;
return node_cnt;
}
// 在节点 x 之后插入节点 y。
void insert_after(int x, int y) {
if (y == 0) return;
int z = nxt[x];
nxt[x] = y;
pre[y] = x;
nxt[y] = z;
if (z != 0) pre[z] = y;
}
// 从链表中摘掉节点 x。
void erase_node(int x) {
int l = pre[x];
int r = nxt[x];
if (l != 0) nxt[l] = r;
if (r != 0) pre[r] = l;
if (head_node == x) head_node = r;
}
// 把段 x 在段内 1-based 偏移 offset 处切开，替换为左右两个新段。
void replace_by_split(int x, int offset) {
int left_len = offset - 1;
int right_len = seg_len[x] - offset;
int old_start = start_pos[x];
int left_node = new_node(old_start, left_len);
int right_node = new_node(old_start + offset, right_len);
int l = pre[x];
int r = nxt[x];
if (l != 0) nxt[l] = 0;
if (r != 0) pre[r] = 0;
if (l != 0) {
nxt[l] = r;
if (r != 0) pre[r] = l;
}
erase_node(x);
// 按顺序把新段插回原位置。
int first = 0;
int last = l;
if (left_node != 0) {
if (l != 0) insert_after(l, left_node);
else head_node = left_node;
first = left_node;
last = left_node;
}
if (right_node != 0) {
if (last != 0) insert_after(last, right_node);
else head_node = right_node;
if (first == 0) first = right_node;
last = right_node;
}
if (last != 0) {
nxt[last] = r;
if (r != 0) pre[r] = last;
}
else {
if (l != 0) nxt[l] = r;
if (r != 0) pre[r] = l;
if (l == 0) head_node = r;
}
}
// 定位本轮要删除的排名：1^3, 2^3, ... 递增，用 cur 指针从链表头往后扫。
// 只记录删除点（节点 + 段内偏移），本轮内不修改链表。
void locate_deleted_positions(int len) {
delete_cnt = 0;
int cur = head_node;
int passed = 0; // cur 段之前所有段的总长度，即 cur 段起点在序列中的排名减 1
for (long long x = 1; x * x * x <= len; x++) {
int rank_pos = (int)(x * x * x);
while (cur != 0 && passed + seg_len[cur] < rank_pos) {
passed += seg_len[cur];
cur = nxt[cur];
}
int offset = rank_pos - passed;
delete_cnt++;
deleted_node[delete_cnt] = cur;
deleted_offset[delete_cnt] = offset;
deleted_value[delete_cnt] = a[start_pos[cur] + offset - 1];
}
}
// 按上一轮定位到的删除点，统一把受影响的段切开。
// 同一轮中一个段可能被多个删除点命中，按段分组后一次性处理。
void apply_deletions() {
int i = 1;
while (i <= delete_cnt) {
int x = deleted_node[i];
int old_start = start_pos[x];
int old_len = seg_len[x];
int l = pre[x];
int r = nxt[x];
// 收集落在段 x 内的所有删除偏移。
vector<int> offsets;
while (i <= delete_cnt && deleted_node[i] == x) {
offsets.push_back(deleted_offset[i]);
i++;
}
// 按偏移从小到大，把段切成若干"保留段"，中间夹着的删除点全部去掉。
int first_new = 0;
int last_new = 0;
int last_cut = 0; // 上一个删除点，新的保留段从它之后开始
for (int j = 0; j < (int)offsets.size(); j++) {
int off = offsets[j];
int keep_len = off - last_cut - 1;
int node = new_node(old_start + last_cut, keep_len);
if (node != 0) {
if (first_new == 0) first_new = node;
if (last_new != 0) insert_after(last_new, node);
last_new = node;
}
last_cut = off;
}
// 最后一个删除点之后到段尾的剩余部分。
int tail_len = old_len - last_cut;
int tail_node = new_node(old_start + last_cut, tail_len);
if (tail_node != 0) {
if (first_new == 0) first_new = tail_node;
if (last_new != 0) insert_after(last_new, tail_node);
last_new = tail_node;
}
// 用新段序列替换掉链表中的旧段 x。
if (l != 0) nxt[l] = first_new;
else head_node = first_new;
if (first_new != 0) pre[first_new] = l;
if (last_new != 0) {
nxt[last_new] = r;
if (r != 0) pre[r] = last_new;
}
else {
if (l != 0) nxt[l] = r;
if (r != 0) pre[r] = l;
if (l == 0) head_node = r;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// 初始整个序列是一个段：原数组 [1, n]。
node_cnt = 0;
head_node = new_node(1, n);
int len = n; // 当前剩余序列长度
while (len > 0) {
// 先只定位本轮删除点，再统一切开，保证"同时删除"。
locate_deleted_positions(len);
vector<int> values;
for (int i = 1; i <= delete_cnt; i++) values.push_back(deleted_value[i]);
rounds.push_back(values);
apply_deletions();
len -= delete_cnt;
}
cout << rounds.size() << '\n';
for (int i = 0; i < (int)rounds.size(); i++) {
for (int j = 0; j < (int)rounds[i].size(); j++) {
if (j) cout << ' ';
cout << rounds[i][j];
}
cout << '\n';
}
return 0;
}复杂度
时间复杂度与每轮段数总扫描量有关。它原地维护段结构，能避免保存完整当前序列，但严格最坏界同样不如树状数组清晰。
空间复杂度为
解法三：树状数组维护动态排名
思路
树状数组是本题的正式主解。它不显式保存当前序列，而是在原数组下标上维护一个存活标记：还在当前序列中的位置为 1，已经删除的位置为 0。
这样，树状数组前缀和就表示某个原下标之前还有多少个元素存活。通过树状数组的 kth 查询，就能快速找到“当前第
每一轮要特别注意同时删除：先枚举所有满足 kth 查出这些排名对应的原下标，全部保存下来；这一阶段不能修改树状数组。等本轮所有要删的位置都确定后，再统一把这些位置从树状数组中减掉。
因为 a[pos] 就满足每行按原序列先后顺序输出。
代码
cpp
/**
* 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-08-11 07:37
* update_at: 2026-08-12 14:07
*/
// main.cpp：正式主解，用树状数组维护每个原位置是否存活，kth 查询定位当前第 k 个元素。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n;
int a[MAXN]; // 原数组，a[i] 存第 i 个位置的元素值
int tree_array[MAXN]; // 树状数组：对每个原位置维护存活标记（1 存活、0 已删除），前缀和 = 当前位置之前的存活个数
int lowbit(int x) {
return x & -x;
}
void add(int pos, int val) {
for (int i = pos; i <= n; i += lowbit(i)) tree_array[i] += val;
}
// 找到当前剩余序列中排名第 k 的元素对应的原数组下标。
// 利用树状数组前缀和单调性，二分倍增跳过大段。
int kth_alive(int k) {
int pos = 0;
int sum = 0;
for (int step = 1 << 20; step > 0; step >>= 1) {
int next_pos = pos + step;
if (next_pos <= n && sum + tree_array[next_pos] < k) {
pos = next_pos;
sum += tree_array[next_pos];
}
}
return pos + 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// 初始时所有位置都存活，树状数组第 i 个位置的值直接等于 lowbit(i)。
for (int i = 1; i <= n; i++) tree_array[i] = lowbit(i);
vector<vector<int> > rounds;
int len = n; // 当前剩余序列的长度
while (len > 0) {
// 第一阶段：只定位本轮要删除的位置，不改树状数组，保证"同时删除"。
vector<int> deleted_pos;
for (long long x = 1; x * x * x <= len; x++) {
int rank_pos = (int)(x * x * x);
deleted_pos.push_back(kth_alive(rank_pos));
}
// 排名递增，查出的原下标也递增，直接按顺序输出即为本轮删除序列。
vector<int> values;
for (int i = 0; i < (int)deleted_pos.size(); i++) {
values.push_back(a[deleted_pos[i]]);
}
rounds.push_back(values);
// 第二阶段：统一把本轮删除的位置标记为 0。
for (int i = 0; i < (int)deleted_pos.size(); i++) {
add(deleted_pos[i], -1);
}
len -= (int)deleted_pos.size();
}
cout << rounds.size() << '\n';
for (int i = 0; i < (int)rounds.size(); i++) {
for (int j = 0; j < (int)rounds[i].size(); j++) {
if (j) cout << ' ';
cout << rounds[i][j];
}
cout << '\n';
}
return 0;
}复杂度
每个元素恰好被删除一次，因此总共会进行 kth 查询和
树状数组、原数组和输出结果共占
复杂度对比
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 双队列流式重建连续段 | 与每轮段数总扫描量有关 | 代码直观，实测可过，但最坏界不如树状数组清晰 | |
| 链表维护连续段 | 与每轮段数总扫描量有关 | 原地维护段结构，细节较多 | |
| 树状数组维护动态排名 | 正式主解，复杂度证明最稳定 |
总结
这题的共同核心是把“当前排名”映射回“原数组中的元素”。三种解法的区别在于维护当前序列的方式。
双队列分段保留了暴力“从旧序列生成新序列”的直觉；链表分段展示了如何原地维护连续段；树状数组则把当前序列隐式成原位置的存活标记，用 kth 查询完成动态排名定位。
正式推荐先掌握树状数组版本，因为它的复杂度证明最稳。两个分段版本适合作为理解动态序列结构的补充。
图示解析
这张图比较三种解法如何完成同一个排名定位目标：
text
共同目标：把当前排名映射回原数组位置
|- 双队列分段
| `- 本轮旧段 q1 -> 删除立方排名 -> 下一轮新段 q2
|- 链表分段
| `- 连续段链表 -> 记录待删偏移 -> 切分受影响段
`- 树状数组
`- 原位置存活标记 -> kth 查询当前第 k 个三种解法都在解决同一个问题：如何把“当前第 kth 查询完成排名定位。