题解：P17233 [Algo Beat Contest 017 B] 线性筛

Build_Dreams · 2026-08-10 17:52:55 · 题解

一拍脑袋就会了。

我们考虑树状数组去维护前 i 个数中还有多少个数没被删掉，然后我们注意到这个数字显然是单调的，于是如果我们要找当前序列中第 x 个数字可以二分做。

细节是我们二分必须找第一个满足前面还没被删的位置，因为可能会是 x，x+1，而 x+1 已经被删掉了，那么 x 和 x+1 前面没被删的数字个数是一样的。

代码很好写。

// <DATETIME>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1e6 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18, RMX = 2324814;
mt19937 rd(time(0));
uniform_int_distribution<int> dist(0, RMX);

int n, a[N];
bool vis[N];
int cnt = 0;

struct BIT{
    int tr[N];
    void modify(int pos, int x){
        while (pos < N){
            tr[pos] += x;
            pos += pos & (-pos);
        }
    }
    int query(int pos){
        int res = 0;
        while (pos){
            res += tr[pos];
            pos -= pos & (-pos);
        }
        return res;
    }
} tr;

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], tr.modify(i, 1);
    // for (int i = 1; i <= n; i ++ ) a[i] = i;

    vector <int> vec;
    for (int i = 1; i * i * i <= n; i ++ ) vec.push_back(i * i * i), cnt ++, tr.modify(i * i * i, -1);
    // cout << tr.query(1) << "\n";

    vector <vector <int>> qwq;
    qwq.push_back(vec);
    while (cnt < n){
        /*
        // for (int i = 0; i < vec.size(); i ++ ) vec[i] += i + 1;

        int add = 0;
        for (int i = 0; i < vec.size(); i ++ ){
            add ++ ;
            while (vec[i] + add <= n && vis[vec[i] + add]) add ++ ;
            if (vec[i] + add > n){
                int cnt = vec.size() - i;
                while (cnt -- ) vec.pop_back();
                break;
            }

            vec[i] += add;
        }

        qwq.push_back(vec);
        for (auto i : vec) cnt ++, vis[i] = 1;
        */

        vec.clear();
        int lst = n - cnt;
        for (int i = 1; i * i * i <= lst; i ++ ){
            // cout << "---------------\n";
            int ned = i * i * i;
            // cout << ned << " qwq\n";

            int l = 1, r = n, ans = n;
            while (l <= r){
                int mid = (l + r) >> 1;
                // cout << mid << " " << tr.query(mid) << "\n";
                if (tr.query(mid) >= ned) ans = mid, r = mid - 1;
                else l = mid + 1;
            }
            vec.push_back(ans);
        }

        qwq.push_back(vec);
        for (auto i : vec) cnt ++, tr.modify(i, -1);
    }

    cout << qwq.size() << "\n";
    for (auto i : qwq){
        for (auto j : i)
            cout << a[j] << " ";
        cout << "\n";
    }
}