bzoj 3439: Kpm的MC密码

.

题意：给出一些串，问以每个串为后缀的串中第k小的编号。
题解：trie+dfs序+主席树
倒序把trie建出来，询问就是求子树中第k小，dfs序+主席树搞搞就好了。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,num=0,ien=0,l[300010],r[300010],nn=0,root[300010],pos[100010];
struct tree
{
    int lc,rc,c;
}tr[10000010];
struct trie
{
    int s[26];
    vector<int>c;
}ie[300010];

int trie_add(string s)
{
    int x=0;
    for(string::reverse_iterator it=s.rbegin();it!=s.rend();it++)
    {
        if(!ie[x].s[*it-'a'])
        ie[x].s[*it-'a']=++ien;
        x=ie[x].s[*it-'a'];
    }
    return x;
}
int ins(int ori,int i,int l,int r,int p)
{
    if(!i||i==ori)
    {
        i=++num;
        tr[i]=tr[ori];
    }
    tr[i].c++;
    if(l==r)
    return i;
    int md=l+r>>1;
    if(p<=md)
    tr[i].lc=ins(tr[ori].lc,tr[i].lc,l,md,p);
    else
    tr[i].rc=ins(tr[ori].rc,tr[i].rc,md+1,r,p);
    return i;
}
int get(int ori,int i,int l,int r,int k)
{
    int size=tr[i].c-tr[ori].c,lsize=tr[tr[i].lc].c-tr[tr[ori].lc].c,md=l+r>>1;
//    cout<<"l:"<<l<<' '<<"r:"<<r<<' '<<"size:"<<size<<endl;
    if(k>size)
    return -1;
    if(l==r)
    return l;
    if(k<=lsize)
    return get(tr[ori].lc,tr[i].lc,l,md,k);
    else
    return get(tr[ori].rc,tr[i].rc,md+1,r,k-lsize);
}
void dfs(int x)
{
    l[x]=++nn;
    root[nn]=root[nn-1];
    for(vector<int>::iterator it=ie[x].c.begin();it!=ie[x].c.end();it++)
    root[nn]=ins(root[nn-1],root[nn],1,n,*it);
    for(int i=0;i<26;i++)
    if(ie[x].s[i])
    dfs(ie[x].s[i]);
    r[x]=nn;
}
int main()
{
//    ios::sync_with_stdio(false);
//    cin>>n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        ie[pos[i]=trie_add(s)].c.push_back(i);
    }
    dfs(0);/*
    for(int i=1;i<=n;i++)
    cout<<pos[i]<<endl;
    for(int i=1;i<=ien;i++)
    cout<<l[i]<<' '<<r[i]<<endl;;*/
    for(int i=1;i<=n;i++)
    {
        int x;
//        cin>>x;
        scanf("%d",&x);
        printf("%d\n",get(root[l[pos[i]]-1],root[r[pos[i]]],1,n,x));
//        cout<<get(root[l[pos[i]]-1],root[r[pos[i]]],1,n,x)<<endl;
    }/*
    for(int i=1;i<=nn;i++)
    {
        for(int j=1;j<=n;j++)
        cout<<get(0,root[i],1,n,j)<<' ';
        cout<<endl;
    }*/
}