题解：P17233 [Algo Beat Contest 017 B] 线性筛
FlowerAccepted
·
·
题解
0x00 前言
这啥题目名字啊 QwQ，筛完了
0x01 解题思路
拿到题目马上注意到我们的立方，而不是平方，也就是说直接维护全部用来删除的完全立方数下标指针，复杂度完全没问题。
每一轮操作互不影响，所以可以一轮一轮去操作。
生成初始指针直接把所有小于等于 n 的 a^3 扔到 vector 里头。
每一轮完成后，第一个指针 \operatorname{poss}_0（就是原来的 1，为了 vector 用着方便就 0-based），原来的位置已经被删掉了，于是来到了往后数第一个位置，下一轮就得从 \operatorname{poss}_0 + 1^{\tiny[1]} 的位置删。第一个指针 \operatorname{poss}_1（原来的 8），原来的位置已经被删掉了，前面 \operatorname{poss}_0 也已经删掉一个了，所以得多走一步，下一轮就得从 \operatorname{poss}_0 + 2 的位置删。同理的，第 i + 1 个指针 \operatorname{poss}_i 要往后走 i + 1 步。
指针很大，数组不堪，会有指针移到末尾然后变成棍母的情况。这里有单调性，前面的指针没了后面的还能留着吗，于是**一旦发现有指针已经到了末尾，就直接删掉他和他后面的所有指针**。
但是这样处理下去有个严重的问题，如果一个指针被顺延到已经被删掉的位置怎么办？
笔者开始想到用 `bitset` $\operatorname{vis}$ ，暴力跳，但是不好写，复杂度还要炸。于是掏出祖传的~~经典图论~~：
**链表思想**。
那么解就显而易见了，设 $\operatorname{nxt}_i$ 表示 $i$ 后面第一个还健在的下标（包括 $n$ 后面的 $n + 1$），每次把 $a_{\operatorname{poss}_i}$ 删除后使 $\operatorname{nxt}_{i-1}\gets\operatorname{nxt}_{i}$ 就行。然后就跳跳。
注意这里可以直接用 $i - 1$，用她而不用存链表上一项是因为手玩一下，就可以注意到每次要么把这块已经删掉的部分删光，要么之前一个位置一定还存在（~~Zako 的废话~~！如果假了欢迎 Hack）。
具体细节可以看代码。
# 0x02 代码呈现
```cpp line-numbers
#include "bits/stdc++.h"
using namespace std;
#define ch(opt, tar, ...) (tar = opt({tar, __VA_ARGS__}))
#define inlfc __attribute__((always_inline)) inline
#define isz(x) ((int)x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MAXN = 1e6 + 5;
int a[MAXN], nxt[MAXN];
vector<int> poss;
vector<vector<int>> ans;
inlfc ll read() {
ll res = 0;
char ch = 0;
while ((ch = getchar_unlocked()) && !isdigit(ch));
do res = (res << 3) + (res << 1) + (ch - '0');
while ((ch = getchar_unlocked()) && isdigit(ch));
return res;
}
int main() {
int n, cnt;
cnt = n = read();
for (int i = 1; i <= n; i ++) {
a[i] = read();
nxt[i] = i + 1; // initialize
}
// 前面讲解用 a^3 是因为用 i^3 太诡异了，我无法保证你不把她当成 -\sqrt{-1}。
for (int i = 1; i * i * i <= n; i ++)
poss.push_back(i * i * i); // 扔进去
while (cnt > 0) { // 还有健在的元素
ans.push_back(vector<int>());
for (int i = 0; i < poss.size(); i ++) {
auto &pos = poss[i];
cnt --; // 健在的元素删掉一个
ans.back().push_back(a[pos]); // 当前行是在 ans 尾部的
nxt[pos - 1] = nxt[pos]; // 神奇
for (int j = 1; j <= i + 1; j ++) // 注意 0-based
if (pos < n) pos = nxt[pos]; // 这里如果是等于那么下回把 a_{n + 1} 删掉就触发海妖了
else {
poss.erase(poss.begin() + i, poss.end());
break; // 全弹掉！
}
}
}
printf("%d\n", ans.size());
for (auto col : ans) { // 自动推导好用
for (auto pos : col)
printf("%d ", pos);
putchar_unlocked('\n');
}
return 0;
}
```
# 0x03 复杂度分析
首先每个原数组中的元素都要遍历到至少一次，所以复杂度就是 $\mathcal O(n)$ 起步，每次跳链表最多最多跳指针数量次，复杂度不大于 $\mathcal O(\sqrt[3]{n})$，所以综合起来就是 $\mathcal O(n\sqrt[3]{n})$，a.k.a $\mathcal O(n^{\frac{4}{3}})$，实际远远跑不满。
代码含快读快写，最大点加不加快读都是一两百毫秒，可见代码本身跑的飞快。所以不要鄙视 STL 了说她常数大了。
# 0x~0 后记
笔者赛时写完此题已经四十分钟了，可见还是太 Zako 了。