题解 P4901 【排队】

· · 题解

%%%……这道题蒟蒻想了好久啊…

写个题解纪念下，同时也为和我一样看不懂出题人题解的oier们指点一条新的道路

肯定还是要先预处理出每个数质因数的个数，这个用线性筛可以解决，因为它是一个“和性函数”。此外，还要预处理出斐波那契数列，大概40个吧。

我们可以建立一个数组a，如果这个数x还没有被选过，a[x]就为1，反之a[x]则为0,建立一个树状数组c记a的前缀和。

假设Ni是maxn，num[w][j]表示第w行第j个编号为多少，sum[w][j]表示第w行前j个数的质因数个数的前缀和，那么询问的时候答案就是sum[ki][r]，r就是在num[w]中小于等于Ni的最大值的下标。（即upper\_bound(Ni)-1）

那么sum怎么预处理呢？

我们可以知道，第w行的第1个数即为选完w-1行后剩下来的第1个数，第2个即为选完w-1行后剩下来的第2个数，第j个即为剩下来的第j个预处理出的斐波那契数。而处理完第j-1个数之后，那个位置上的a[x]会变成0，那我们要找到第j个数是什么，只要找到一个p，使得p在a的前缀和恰好等于fib[j]-j+1即可（这里理解一下啊），然后我们就可以预处理出sum以及num数组了。

但是问题又来了：怎么找呢？

笔者一开始想到的是\log^2{n}的树状数组+二分，但是感觉会T，于是冥思苦想+学习了树状数组加倍增的精妙写法……主要代码在下面，相信学过倍增和树状数组的oier们都能看懂…

int t=(1<<22),pos=0;
    int tot=0;
    for(;t;t>>=1){
        if(tot+c[t+pos]<x){
            pos+=t;
            tot+=c[pos];
        } 
    }
    return pos+1;

这是一种非常实用的方法，在许多题目里都可以用来减少一个\log{n}的复杂度

大家一定都明白了吧！

时间复杂度：O(n\log{n}+T\log{n})

最后吐槽一点，按照我随性的代码风格，卡空间这种操作令我痛不欲生啊……

下面是完整代码（部分变量名可能与题解里的不同，大家看懂就好）

#include<bits/stdc++.h>
using namespace std;
template<typename T>void Read(T &x){
    x=0;int f=1;char s=getchar();
    while(!isdigit(s)){if(s=='-') f=-1;s=getchar();}
    while(isdigit(s)){x=x*10+s-'0';s=getchar();}
    x*=f;
}
const int maxn=5*1e6,maxk=1e4,fbnq_size=45;
int c[maxn+10],p[100];
inline int lowbit(int x){
    return x&-x;
}
void add(int x,int y){
    for(;x<=maxn;x+=lowbit(x)) c[x]+=y;
}
int pri[maxn/10];
bitset<maxn+10> fac;
short d[maxn+10];
int siz=0;
void do_d(){
    for(int i=2;i<=maxn;i++){
        if(fac[i]==0){
            pri[++siz]=i;
            d[i]=1;
        }
        for(int j=1;j<=siz;j++){
            if(i*pri[j]>maxn) break;
            fac[i*pri[j]]=1;
            d[i*pri[j]]=d[i]+1;
            if(i%pri[j]==0) break;
        }
    }
}
vector<int> sum[maxk+10];
vector<int> num[maxk+10];
int find_num(int x){
    int t=(1<<22),pos=0;
    int tot=0;
    for(;t;t>>=1){
        if(tot+c[t+pos]<x){
            pos+=t;
            tot+=c[pos];
        } 
    }
    return pos+1;
}
void pre_process(){
    do_d();
    p[1]=1;p[2]=2;
    for(int i=3;i<=fbnq_size;i++) p[i]=p[i-1]+p[i-2];
    for(int i=1;i<=maxn;i++){
        add(i,1);
    } 
    int tot=maxn;
    for(int i=1;i<=maxk;i++){
        for(int j=1;tot>=p[j]-j+1;j++){
            int pos=find_num(p[j]-j+1);
            add(pos,-1);tot--;
            if(j==1) sum[i].push_back(d[pos]);
            else{
                int x=sum[i][j-2]+d[pos];
                sum[i].push_back(x); 
            } 
            num[i].push_back(pos); 
        }
    }
}
int main(){
    pre_process();
    int T;
    Read(T);
    for(int t=1;t<=T;t++){
        int n,k;
        Read(n);Read(k);
        if(num[k][0]>n) printf("%d\n",-1);
        else{
            int pos=upper_bound(num[k].begin() ,num[k].end() ,n)-num[k].begin() -1;
            printf("%d\n",sum[k][pos]);
        }
    } 
    return 0;
}