题目地址：BZOJ：Problem 3439. — Kpm的MC密码

题目描述

Kpm当年设下的问题是这样的：
现在定义这么一个概念，如果字符串s是字符串c的一个后缀，那么我们称c是s的一个kpm串。
系统将随机生成n个由a…z组成的字符串，由1…n编号（s1,s2…,sn），然后将它们按序告诉你，接下来会给你n个数字，分别为k1…kn，对于每一个ki，要求你求出列出的n个字符串中所有是si的kpm串的字符串的编号中第ki小的数，如果不存在第ki小的数，则用-1代替。（比如说给出的字符串是cd,abcd,bcd,此时k1=2，那么”cd”的kpm串有”cd”,”abcd”,”bcd”,编号分别为1,2,3其中第2小的编号就是2）（PS：如果你能在相当快的时间里回答完所有n个ki的查询，那么你就可以成功帮kpm进入MC啦~~）

题意简述

给n个字符串，按1~n编号。对于每一个字符串s，询问s是后缀的字符串中，编号第k大的编号。

输入输出格式

输入格式：
第一行一个整数 n 表示字符串的数目
接下来第二行到n+1行总共n行，每行包括一个字符串，第i+1行的字符串表示编号为i的字符串
接下来包括n行，每行包括一个整数ki，意义如上题所示

输出格式：
包括n行，第i行包括一个整数，表示所有是si的kpm串的字符串的编号中第ki小的数

输入输出样例

输入样例#1：

3
cd
abcd
bcd
2
3
1

输出样例#1：

2
-1
2

说明

样例解释
“cd”的kpm 串有”cd”,”abcd”,”bcd”,编号为1,2,3，第2小的编号是2，”abcd”的kpm串只有一个，所以第3小的编号不存在，”bcd”的kpm串有”abcd”,”bcd”,第1小的编号就是2。
数据范围与约定
对于100%的数据，1<=n<=100000

题解

要查后缀是某串的字符串有哪些，自然可以想到反着插入Trie树，找该串末结点对应的子树中的结尾标记。既然是子树查询k大，我们可以按DFS序建主席树来查。
复杂度O(n \log n)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 100005;

int ch[MAXN][26], ed[MAXN], tot;
int head[MAXN], val[MAXN], nxt[MAXN], ltot;

inline void insert(char *str, int id) {
    int n = strlen(str + 1), p = 0;
    for(int i = n; i >= 1; i--) {
        int t = str[i] - 'a';
        if(!ch[p][t]) ch[p][t] = ++tot;
        p = ch[p][t];
    }
    val[++ltot] = id; nxt[ltot] = head[p]; head[p] = ltot; ed[id] = p;
}

int dfn[MAXN], vn[MAXN], siz[MAXN], clk;

inline void dfs(int u) {
    dfn[u] = ++clk; vn[dfn[u]] = u;
    siz[u] = 1;
    for(int i = 0; i < 26; i++) {
        if(ch[u][i]) {
            dfs(ch[u][i]); siz[u] += siz[ch[u][i]];
        }
    }
}

struct Node {
    int lch, rch, val, id;
} tr[MAXN << 4];
int rt[MAXN], stot;

inline void insert(int &o, int l, int r, int x, int id) {
    if(tr[o].id != id) {
        tr[++stot] = tr[o]; o = stot; tr[o].id = id;
    }
    tr[o].val++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tr[o].lch, l, mid, x, id);
    else insert(tr[o].rch, mid + 1, r, x, id);
}

inline int query(int o1, int o2, int l, int r, int k) {
    if(l == r) return l;
    int mid = (l + r) >> 1, lsiz = tr[tr[o2].lch].val - tr[tr[o1].lch].val;
    if(k <= lsiz) return query(tr[o1].lch, tr[o2].lch, l, mid, k);
    else return query(tr[o1].rch, tr[o2].rch, mid + 1, r, k - lsiz);
}

int n, k;
char s[MAXN];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        insert(s, i);
    }
    dfs(0);
    for(int i = 1; i <= clk; i++) {
        rt[i] = rt[i - 1];
        for(int j = head[vn[i]]; j; j = nxt[j]) {
            insert(rt[i], 1, n, val[j], i);
        }
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &k);
        if(tr[rt[dfn[ed[i]] + siz[ed[i]] - 1]].val - tr[rt[dfn[ed[i]] - 1]].val < k) {
            puts("-1"); continue;
        }
        printf("%d\n", query(rt[dfn[ed[i]] - 1], rt[dfn[ed[i]] + siz[ed[i]] - 1], 1, n, k));
    }
    return 0;
}