【BZOJ3439】Kpm的MC密码 trie树+主席树

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

HINT

Source

Kpmcup#0 By Greens

  阻止我1A的元凶,没输换行符,不过确实在询问完就输出这样子看不粗来呀,长见识了,这道题也让我长见识了。

  思路当时倒是想到了大概,但完全不会写,,%了OXer的题解,感觉好多了。

  首先反着建trie树,这样所有答案就包含在这棵树的子树里了,注意处理每个字符串的位置,然后再直接套上主席树求区间第K大就OK了。PS:树据结构还是得多写啊,感觉既锻炼码力又锻炼思维。

 #include <iostream>
#include <cstdio>
#include <cstring>
#define N 300010
using namespace std;
struct data{int next,to;}e[N*];
int root[N],lch[N*],rch[N*],cnt[N*],head[N],in[N],out[N],a[N];
int ch[N][];
int n,tot,num;
char s[N];
void se(int x,int y) {tot++; e[tot].next=head[x]; e[tot].to=y; head[x]=tot;}
void part1_insert(int p)
{
int len=strlen(s),x=;
for (int i=len-;i>=;i--)
if (ch[x][s[i]-'a']) x=ch[x][s[i]-'a'];
else ch[x][s[i]-'a']=++num,x=num;
se(x,p);
}
void part2_mark(int x)
{
int num=tot;
for (int i=head[x];i;i=e[i].next) a[++tot]=e[i].to;
for (int i=;i<;i++) if (ch[x][i]) part2_mark(ch[x][i]);
for (int i=head[x];i;i=e[i].next) in[e[i].to]=num,out[e[i].to]=tot;
}
int change(int x,int l,int r,int v)
{
int now=++tot;
if (l==r)
{
cnt[now]=cnt[x]+;
lch[now]=rch[now]=;
}
else
{
int mid=(l+r)>>;
if (v<=mid)
{
rch[now]=rch[x];
lch[now]=change(lch[x],l,mid,v);
}
else
{
lch[now]=lch[x];
rch[now]=change(rch[x],mid+,r,v);
}
cnt[now]=cnt[lch[now]]+cnt[rch[now]];
}
return now;
}
void part3_build() {for (int i=;i<=n;i++) root[i]=change(root[i-],,n,a[i]);}
int query(int root1,int root2,int l,int r,int k)
{
if (l==r) return l;
if (cnt[root2]-cnt[root1]<k) return -;
int mid=(l+r)>>;
if (cnt[lch[root2]]-cnt[lch[root1]]>=k) return query(lch[root1],lch[root2],l,mid,k);
else return query(rch[root1],rch[root2],mid+,r,k-(cnt[lch[root2]]-cnt[lch[root1]]));
}
void part4_query()
{
for (int i=;i<=n;i++)
{
int k;
scanf("%d",&k);
printf("%d\n",query(root[in[i]],root[out[i]],,n,k));
}
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%s",s);
part1_insert(i);
}
tot=;
part2_mark();
tot=;
root[]=cnt[]=lch[]=rch[]=;
part3_build();
part4_query();
return ;
}
上一篇:Chrome升级91扩展程序报错Tabs cannot be edited right now (user may be dragging a tab)解决方法


下一篇:03JavaScript程序设计修炼之道 2019-06-23_15-50-11 验证码