这题让我升华。。还好只重构了一遍

---

首先我们发现：$n$较小时，整个队伍的形态 跟 $n$ 比较大时的局部是一样的

所以我们预处理出这个队伍的形态，和每一行每个位置的质因子个数的前缀和，$O(nlogn)$，然后每次回答$log(n)$

方法：

1.线性筛，筛出每个数值因子的个数；

2.然后用一个树状数组，维护整个队列中的还存在的数的数量；相当于统计一个数组（设其为$a$）的前缀和，这个数组以自己为下标，存储这个数还存不存在，即$a[x]=1表示x存在，a[x]=0表示x不存在$；刚开始$a$中都为$1$，当某个数$x$被删除时，单点修改$a[x]=0$.

3.查询排名：这里要用到倍增的思路。因为当树状数组的下标$pos==2^k$时，它维护的是$[1,2^k]$的前缀和，所以根据树状数组的思想，可以倍增查找；

4.因为每次查询后都会删一个数，所以查询的实际位置是$fib[i]-已经删去的数的个数，即fib[i]-i+1$

5.最后对于每一个询问，在预处理出的 队伍形态 的数组的第$k$行中，查找编号小于但最接近$n$的那个数数的位置，对应到前缀和数组中的位置就是答案。

但是自己还有个疑问：为何空间开一半就够了。。。自己一直MLE，看了题解才开了一半qwq

PS：bitset比bool 快一些

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define R register intconst int N=5000000,K=10000;using namespace std;inline int g() {    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;}int c[N+1],fib[38];inline int lbt(int x) {
   return x&-x;}inline void add(int pos,int vl) {
   for(;pos<=N;pos+=lbt(pos)) c[pos]+=vl;}int pri[N/11],tot;short cnt[N+1];bitset
          
            vis;inline void PRI() { for(R i=2;i<=N;++i) { if(!vis[i]) pri[++tot]=i,cnt[i]=1; for(R j=1;j<=tot&&i*pri[j]<=N;++j) { vis[i*pri[j]]=true,cnt[i*pri[j]]=cnt[i]+1; if(i%pri[j]==0) break; } } }vector
           
             sum[K+1],num[K+1];inline int query(int rk) { R pos=0,tot=0; for(R t=22;t>=0;--t) if(tot+c[pos+(1<
            
             
              =2) sum[i].push_back(sum[i][j-2]+cnt[pos]); else sum[i].push_back(cnt[pos]); num[i].push_back(pos); }}signed main() { PRE(); R t=g(); for(R i=1;i<=t;++i) { R n=g(),k=g(); if(num[k][0]>n) {printf("-1\n"); continue;} R pos=upper_bound(num[k].begin(),num[k].end(),n)-num[k].begin()-1; printf("%d\n",sum[k][pos]); } //while(1);}
             
            
           
          
         
        
       
      
     

---

2019.05.17