RE了几十发，实在没办法了…只好向管理员要数据，然后发现数据规模与题目描述不符…

建立Trie并求出DFS序，同时根据DFS序确定字典序

然后每次询问相当于询问子树第k小，用主席树维护，注意压缩内存

时间复杂度$O(L+n\log w)$，L为所有串长度之和

 

#include
     
      #include
      
       const int N=100010,T=2100000,M=2000010;int n,q,i,k,v[T],st[T],en[T],tot,dfn,now,root[T],l[M],r[M],cnt,val[M],a[N],b[N],seq[T];int g[T],nxt[T],to[T],ed;char s[T],ch[T],w[T];inline void addedge(int x,int y,int z){to[++ed]=y,w[ed]=z;nxt[ed]=g[x];g[x]=ed;}inline int son(int x,int y){  for(int i=g[x];i;i=nxt[i])if(w[i]==y)return to[i];  return 0;}inline void ins(int p){  for(int x=0,i=0,j=std::strlen(s),w;i
       
        >1;  if(c<=mid)l[y]=add(l[x],a,mid,c),r[y]=r[x];else l[y]=l[x],r[y]=add(r[x],mid+1,b,c);  return y;}inline int ask(int k){  int x=0,i=0,j=std::strlen(ch),w,y,c=1,d=n,mid;  for(;i
        
         >1,j=val[l[x]]-val[l[y]];    if(k<=j)d=mid,x=l[x],y=l[y];else k-=j,c=mid+1,x=r[x],y=r[y];  }  return b[c];}int main(){  scanf("%d%d",&n,&q);  for(i=1;i<=n;i++)scanf("%s",s),ins(i);  for(dfs(0),i=1;i<=n;i++)b[a[i]]=i;  for(i=1;i<=dfn;i++)root[i]=seq[i]?add(root[i-1],1,n,seq[i]):root[i-1];  while(q--)scanf("%d%s",&k,ch),printf("%d\n",ask(k));  return 0;}