bzoj 3439: Kpm的MC密碼

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

HINT

Source

Kpmcup#0 By Greens

?

題目求的是后綴，那么把串倒過來，就變成前綴問題了，可以考慮trie樹解決。。。

相當于求串的開頭到根節點的路徑上的k值。。。

那么可以trie樹套值域線段樹，動態開節點就好了,每個點都有一個到根的路徑的值域線段樹，然后查詢k值在線段樹上跑一跑就可以了

// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=500050;
int n,trie[N][26],tt,sz,rt[N*20],ls[N*20],rs[N*20],sum[N*20],val[N],ed[N];
char s[N];
void ins(int &x,int l,int r,int v){if(!x) x=++sz;if(l==r){sum[x]++;return;}int mid=(l+r)>>1;if(v<=mid) ins(ls[x],l,mid,v);else ins(rs[x],mid+1,r,v);sum[x]=sum[ls[x]]+sum[rs[x]];
}
void insert(int id){int len=strlen(s+1);int x=0;for(int i=len;i;i--){if(!trie[x][s[i]-'a']) trie[x][s[i]-'a']=++tt;x=trie[x][s[i]-'a'];ins(rt[x],1,n,id);}ed[id]=x;
}
int query(int x,int l,int r,int k){if(l==r){return l;}int mid=(l+r)>>1;if(sum[ls[x]]>=k) return query(ls[x],l,mid,k);else return query(rs[x],mid+1,r,k-sum[ls[x]]);
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);insert(i);}for(int i=1;i<=n;i++){int k;scanf("%d",&k);if(sum[rt[ed[i]]]<k) puts("-1");else printf("%d\n",query(rt[ed[i]],1,n,k));}return 0;
}