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

主席树, 字典树

传送门：BZOJ3439

思路：

  • 先把所有的串倒过来建成字典树；
  • 然后只需要求子树第k小；
  • 用dfs序就转化为了区间第k小；
  • 似乎是静态的，主席树即可。

注意：

  • 主席树不要忘了继承上个节点；
  • 注意字符集大小。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 120000
int n,m,x,cnt,clk,xb,tot,tmp,c[N][30],sum[N*20],ls[N*20],rs[N*20],dfn[N],head[N],nxt[N],v[N],ll[N],rr[N],pos[N],rt[N];
char s[N];
int getint(){
	char ch; int sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
void ins(int &root,int root2,int l,int r,int k){
	sum[root=++cnt]+=sum[root2];
	if (l==r){sum[root]++; return;}
	int mid=(l+r)>>1;
	if (k<=mid){rs[root]=rs[root2]; ins(ls[root],ls[root2],l,mid,k);}
	if (k>mid){ls[root]=ls[root2]; ins(rs[root],rs[root2],mid+1,r,k);}
	sum[root]=sum[ls[root]]+sum[rs[root]];
}
int query(int root,int root2,int l,int r,int x){
	if (sum[root]-sum[root2]<x) return -1;
	if (l==r) return l;
	int mid=(l+r)>>1;
	if (sum[ls[root]]-sum[ls[root2]]>=x) return query(ls[root],ls[root2],l,mid,x);
	if (sum[ls[root]]-sum[ls[root2]]<x) return query(rs[root],rs[root2],mid+1,r,x-(sum[ls[root]]-sum[ls[root2]]));
	return -1;
}
void dfs(int u){
	dfn[u]=ll[u]=rr[u]=++clk;
	if (head[u]){int last=rt[clk-1]; for (int j=head[u];j;j=nxt[j]){ins(rt[clk],last,1,n,v[j]); last=rt[clk];}}
	else rt[clk]=rt[clk-1];//Important
	for (int i=1;i<=26;i++){int v=c[u][i]; if (v){dfs(v); rr[u]=rr[v];}}
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%s",s+1); int len=strlen(s+1); xb=0;
		for (int j=len;j>=1;j--){
			int w=s[j]-'a'+1;
			if (!c[xb][w]) c[xb][w]=++cnt;
			xb=c[xb][w];
		}
		v[++tot]=i; nxt[tot]=head[xb]; head[xb]=tot; pos[i]=xb;
	}
	cnt=0; dfs(0);
	for (int i=1;i<=n;i++){
		x=getint();
		if ((tmp=query(rt[rr[pos[i]]],rt[ll[pos[i]]-1],1,n,x))>0) printf("%d\n",tmp); else puts("-1");
	}
	
	return 0;
}