# Bzoj3439: MC password of KPM (Chairman tree + DFS order + dictionary tree)

2020-12-07 15:04:47

Subject portal
Someone told me to use linked list to do this question . Handle the same string .
It's said on the Internet to ..
No, actually .. Record the end of each string on the dictionary tree .
And then one .

solution ：
Because it's a suffix, so build a dictionary tree here .
then kpm Strings must be all the strings of a subtree .
Then use the chairman tree to maintain the subtree k Small .
It is required that the serial number should be set dfs Just order .

Code implementation ：

``````#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct Trie {

int son[31];Trie() {

memset(son,-1,sizeof(son));}}tr[310000];
int tot,end[110000],root;char ss[310000];
void Build(int k) {
int x=root,len=strlen(ss+1);
for(int i=len;i>=1;i--) {
int y=ss[i]-'a'+1;
if(tr[x].son[y]==-1) {tot++;tr[x].son[y]=tot;}
x=tr[x].son[y];
}
end[k]=x;
}
struct node {

int lc,rc,c;}t[2100000];int cnt,rt[110000];
void build(int &u,int l,int r,int p,int c) {
if(u==0)u=++cnt;t[u].c+=c;
if(l==r)return ;int mid=(l+r)/2;
if(p<=mid)build(t[u].lc,l,mid,p,c);
else build(t[u].rc,mid+1,r,p,c);
}
void Merge(int &u1,int u2) {
if(u1==0){u1=u2;return ;}if(u2==0)return ;
t[u1].c+=t[u2].c;
Merge(t[u1].lc,t[u2].lc);Merge(t[u1].rc,t[u2].rc);
}
int z,st[310000],ed[310000];
void dfs(int x) {
st[x]=++z;
for(int i=1;i<=26;i++)if(tr[x].son[i]!=-1)dfs(tr[x].son[i]);
ed[x]=z;
}
int find(int u1,int u2,int l,int r,int k) {
if(t[u1].c-t[u2].c<k)return -1;
if(l==r)return l;int mid=(l+r)/2;
int c=t[t[u1].lc].c-t[t[u2].lc].c;
if(k<=c)return find(t[u1].lc,t[u2].lc,l,mid,k);
else return find(t[u1].rc,t[u2].rc,mid+1,r,k-c);
}
int find_l(int u1,int u2,int l,int r,int p) {
if(l==r)return t[u1].c-t[u2].c;int mid=(l+r)/2;
int c=t[t[u1].lc].c-t[t[u2].lc].c;
if(p<=mid)return find(t[u1].lc,t[u2].lc,l,mid,p);
else return find(t[u1].rc,t[u2].rc,mid+1,r,p)+c;
}
int main() {
int n;scanf("%d",&n);root=tot=0;
for(int i=1;i<=n;i++) {

scanf("%s",ss+1);Build(i);}
z=0;dfs(root);cnt=0;
for(int i=1;i<=n;i++)build(rt[st[end[i]]],1,n,i,1);
for(int i=1;i<=z;i++)Merge(rt[i],rt[i-1]);
for(int i=1;i<=n;i++) {
int x,k;scanf("%d",&k);x=end[i];printf("%d\n",find(rt[ed[x]],rt[st[x]-1],1,n,k));
}
return 0;
}``````

https://chowdera.com/2020/12/20201207150436878l.html