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

雄关漫道真如铁 · 2026-08-10 17:44:40 · 题解

题目链接：P17233

题目大意

给定一个序列 a_1,a_2,\cdots,a_n，每次操作删去其中下标为完全立方数的元素，直到序列为空。输出总操作次数与每次操作时删去的元素值。

大致思路

数据结构是对的！

考虑利用树状数组解决本题。我们维护一个值仅包含 0,1 的树状数组，用于记录一开始某个位置上的元素是否已经被删除，那么当前序列中下标为 k 的位置，在一开始的序列中，就是树状数组上第一个前缀和恰好等于 k 的位置。这可以使用树状数组上的二分 \mathcal{O}(\log n) 地求出，那么本题是简单的。

最终代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
struct BIT
{
    int n;vector<int> b;
    BIT(int n_){init(n_);}
    void init(int n_){n=n_,b.assign(n+5,0);}
    int lowbit(int x){return x&-x;}
    void update(int pos,int k){while(pos<=n) b[pos]+=k,pos+=lowbit(pos);}
    int kth(int k)
    {
        int pos=0,sum=0;
        for(int i=__lg(n);i>=0;i--)
        {
            int nxt=pos+(1<<i);
            if(nxt>n) continue;
            if(sum+b[nxt]<k) sum+=b[nxt],pos=nxt;
        }
        return pos+1;
    }
};
int n,cnt,a[MAXN];
vector<int> ans[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    BIT b(n);
    for(int i=1;i<=n;i++) cin>>a[i],b.update(i,1);
    while(n)
    {
        cnt++;
        for(int i=1;i*i*i<=n;i++) ans[cnt].push_back(b.kth(i*i*i));
        for(int i:ans[cnt]) b.update(i,-1);
        n-=ans[cnt].size();
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
    {
        for(int j:ans[i]) cout<<a[j]<<' ';
        cout<<endl;
    }
    return 0;
}

让 DeepSeek 分析了一下复杂度。每个元素都恰好调用一次kth，而单次调用kth需要 \mathcal{O}(\log n) 的时间。同时，ans中的元素个数之和也恰好为 n，故总复杂度如下。