BZOJ 3439 Kpm的MC密碼 Trie+可持久化線段樹

題目大意：定義一種串，如果一個串是另一個串的後綴，那麼這個串稱作kpm串。問一個串的標號第k大的kpm串是多少。

思路：將所有的串翻轉之後變成前綴，全都插進一個Trie樹中。每個節點維護一個last指針，表示最後一次更新的可持久化線段樹的指針，如果再有串經過這裡，就繼續更新last指針。最後只需要查詢last指針中的東西就可以了。

CODE：

#include 
#include 
#include 
#include 
#define MAX 300010
using namespace std;
#define P(a) ((a) - 'a')
 
struct SegTree{
    SegTree *son[2];
    int cnt;
     
    SegTree(SegTree *_,SegTree *__,int ___) {
        son[0] = _;
        son[1] = __;
        cnt = ___;
    }
    SegTree() {}
}none,*nil = &none;
 
SegTree *BuildTree(SegTree *last,int l,int r,int x)
{
    if(l == r)  return new SegTree(NULL,NULL,last->cnt + 1);
    int mid = (l + r) >> 1;
    if(x <= mid) return new SegTree(BuildTree(last->son[0],l,mid,x),last->son[1],last->cnt + 1);
    return new SegTree(last->son[0],BuildTree(last->son[1],mid + 1,r,x),last->cnt + 1);
}
 
struct Trie{
    Trie *son[26];
    SegTree *last;
     
    Trie() {
        memset(son,0,sizeof(son));
        last = nil;
    }
}*root = new Trie(),*end_pos[MAX];
 
int cnt;
char s[MAX];
 
inline void Insert(char *s,int p)
{
    Trie *now = root;
    while(*s != '\0') {
        if(now->son[P(*s)] == NULL)
            now->son[P(*s)] = new Trie();
        now = now->son[P(*s)];
        now->last = BuildTree(now->last,1,MAX,p);
        ++s;
    }
    end_pos[p] = now;
}
 
int Ask(SegTree *now,int l,int r,int k)
{
    if(now->cnt < k)  return -1;
    if(l == r)  return l;
    int mid = (l + r) >> 1;
    if(k <= now->son[0]->cnt)  return Ask(now->son[0],l,mid,k);
    return Ask(now->son[1],mid + 1,r,k - now->son[0]->cnt);
}
 
int main()
{
    cin >> cnt;
    nil->son[0] = nil->son[1] = nil;
    for(int i = 1; i <= cnt; ++i) {
        scanf("%s",s);
        reverse(s,s + strlen(s));
        Insert(s,i);
    }
    for(int k,i = 1; i <= cnt; ++i) {
        scanf("%d",&k);
        printf("%d\n",Ask(end_pos[i]->last,1,MAX,k));
    }
    return 0;
}