BZOJ3439 Kpm的MC密码（可持久化trie）

　　将串反过来就变成查询前缀了。考虑建一棵可持久化trie，查询时二分答案，均摊一下复杂度即为O(mlogn)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

#define M 300010

int n,cnt=,root[N],size[N];

vector<int> a[N];

struct data{int ch[],x;

}tree[M<<];

void ins(int &k,int x,int p)

{

    tree[++cnt]=tree[k],k=cnt;tree[k].x++;

    if (p==size[x]) return;

    ins(tree[k].ch[a[x][p]],x,p+);

}

int query(int k,int x,int p)

{

    if (!k) return ;

    if (p==size[x]) return tree[k].x;

    return query(tree[k].ch[a[x][p]],x,p+);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3439.in","r",stdin);

    freopen("bzoj3439.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++)

    {

        char c=getchar();

        while (c<'a'||c>'z') c=getchar();

        while (c>='a'&&c<='z') a[i].push_back(c-'a'),c=getchar();

        root[i]=root[i-];size[i]=a[i].size();

        reverse(a[i].begin(),a[i].end());

        ins(root[i],i,);

    }

    for (int i=;i<=n;i++)

    {

        int x=read();

        int l=,r=n,ans=-;

        while (l<=r)

        {

            int mid=l+r>>;

            if (query(root[mid],i,)>=x) ans=mid,r=mid-;

            else l=mid+;

        }

        printf("%d\n",ans);

    }

    return ;

}