当前位置:网站首页>Bzoj3439: MC password of KPM (Chairman tree + DFS order + dictionary tree)

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

2020-12-07 15:04:47 osc_ uwh2aihq

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;
}

版权声明
本文为[osc_ uwh2aihq]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207150436878l.html