3439: Kpm的MC密码

Time Limit: 15 Sec  Memory Limit: 256 MB

Submit: 984  Solved: 462

[][][]

Description

 背景

    想Kpm当年为了防止别人随便进入他的MC，给他的PC设了各种奇怪的密码和验证问题（不要问我他是怎么设的。。。），于是乎，他现在理所当然地忘记了密码，只能来解答那些神奇的身份验证问题了。。。

 描述

    Kpm当年设下的问题是这样的：

    现在定义这么一个概念，如果字符串s是字符串c的一个后缀，那么我们称c是s的一个kpm串。

    系统将随机生成n个由a…z组成的字符串，由1…n编号（s1,s2…,sn），然后将它们按序告诉你，接下来会给你n个数字，分别为k1…kn，对于每一个ki，要求你求出列出的n个字符串中所有是si的kpm串的字符串的编号中第ki小的数，如果不存在第ki小的数，则用-1代替。（比如说给出的字符串是cd,abcd,bcd,此时k1=2，那么”cd”的kpm串有”cd”,”abcd”,”bcd”,编号分别为1,2,3其中第2小的编号就是2）（PS：如果你能在相当快的时间里回答完所有n个ki的查询，那么你就可以成功帮kpm进入MC啦~~）

Input

 

    第一行一个整数 n 表示字符串的数目

    接下来第二行到n+1行总共n行，每行包括一个字符串，第i+1行的字符串表示编号为i的字符串

    接下来包括n行，每行包括一个整数ki，意义如上题所示

 

Output

 

    包括n行，第i行包括一个整数，表示所有是si的kpm串的字符串的编号中第ki小的数

 

Sample Input

3

cd

abcd

bcd

2

3

1

Sample Output

2

-1

2

样例解释

“cd”的kpm 串有”cd”,”abcd”,”bcd”,编号为1,2,3，第2小的编号是

2，”abcd”的kpm串只有一个，所以第3小的编号不存在，”bcd”的kpm

串有”abcd”,”bcd”,第1小的编号就是2。

数据范围与约定

设所有字符串的总长度为len

对于100%的数据，1<=n<=100000,0<len<=300000

/*    首先很容易想到将字符串倒叙插入Trie树上    然后可以通过dfs+主席树，实现地k大的查询 */#include
      
       #include
       
        #include
        
         #include
         
          #define maxn 500010using namespace std;int cnt,ne[maxn][26],num[maxn],c[maxn],b[maxn],d[maxn],n;char ch[maxn];struct node{    int rc,lc,sum;}tr[maxn<<2];vector
          
           Q[maxn];void insert1(int p){    int l=strlen(ch),cc,now=0;    for(int i=l-1;i>=0;i--){        int t=ch[i]-'a';        if(!ne[now][t])ne[now][t]=++cnt;        now=ne[now][t];    }    num[now]++;    Q[now].push_back(p);}void dfs(int x){    for(int i=0;i
           
            >1; if(v<=mid){ tr[x].lc=++cnt;tr[x].rc=tr[y].rc; insert2(tr[x].lc,tr[y].lc,l,mid,v); } else{ tr[x].rc=++cnt;tr[x].lc=tr[y].lc; insert2(tr[x].rc,tr[y].rc,mid+1,r,v); }}int ask(int l,int r,int L,int R,int v){ if(L==R)return L; int mid=(L+R)>>1,tmp=tr[tr[r].lc].sum-tr[tr[l].lc].sum; if(tmp>=v)return ask(tr[l].lc,tr[r].lc,L,mid,v); else return ask(tr[l].rc,tr[r].rc,mid+1,R,v-tmp);}int main(){ int x; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%s",ch),insert1(i); cnt=0;dfs(0);cnt=n+1; for(int i=1;i<=n;i++)insert2(i+1,i,1,n,d[i]); for(int i=1;i<=n;i++){ scanf("%d",&x); if(tr[b[i]+1].sum-tr[c[i]].sum