首页 > 代码库 > bzoj 3439: Kpm的MC密码
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
cd
abcd
bcd
2
3
1
Sample Output
-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;
}
bzoj 3439: Kpm的MC密码