题目大意：
有n个字符串，编号为1~n，求每一个字符串在其他字符串中以它为后缀的字符串中编号第k小的字符串的编号。
思路：
将字符串倒过来建Trie，记录每个结尾节点的编号（可能会有重复，所以开一个vector记录）。再对trie树进行dfs序，记录结尾节点的子树区间。区间第k小，自然用可持久化线段树（由于权值就是id，所以不用离散化）。 注意：dfs序在遇到结尾节点时才++记录序号的变量cnt，而且相同串的dfs序号是一样的（就是说一个结尾节点可能包含好多个不同编号的串），左区间取最前的一个（比如dfs到x节点，编号为2，x节点存着两个串，那么它们的左区间都为2，而序号要加两次）
参考自：http://blog.csdn.net/xym_CSDN/article/details/51340321
代码：
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#define M 500009
using namespace std;
vector <int> q[M];
int cnt,trie[M][],num[M],com[M],out[M],dat[M],sum[M<<],lc[M<<],rc[M<<];
char s[M]; void ins(int id,char *str)
{
int i,l=strlen(str),j=,k;
for (i=l-;i>=;i--,j=trie[j][k])
if (!trie[j][k=str[i]-'a']) trie[j][k]=++cnt;
num[j]++; q[j].push_back(id);
} void dfs(int x)
{
int i;
for (i=;i<num[x];i++) com[q[x][i]]=cnt+;
for (i=;i<num[x];i++) dat[++cnt]=q[x][i];
for (i=;i<;i++) if (trie[x][i]) dfs(trie[x][i]);
for (i=;i<num[x];i++) out[q[x][i]]=cnt;
} void build(int l,int r,int cur,int _cur,int x)
{
sum[cur]=sum[_cur]+;
if (l==r) return; int mid=l+r>>;
if (x<=mid) lc[cur]=++cnt,rc[cur]=rc[_cur],build(l,mid,lc[cur],lc[_cur],x);
else lc[cur]=lc[_cur],rc[cur]=++cnt,build(mid+,r,rc[cur],rc[_cur],x);
} int ask(int L,int R,int l,int r,int k)
{
if (L==R) return L;
int mid=L+R>>,t=sum[lc[r]]-sum[lc[l]];
if (t>=k) return ask(L,mid,lc[l],lc[r],k);
else return ask(mid+,R,rc[l],rc[r],k-t);
} int main()
{
int n,i,x; scanf("%d",&n);
for (i=;i<=n;i++) scanf("%s",s),ins(i,s);
for (cnt=,dfs(),cnt=n+,i=;i<=n;i++) build(,n,i+,i,dat[i]);
for (i=;i<=n;i++)
{
scanf("%d",&x);
if (sum[out[i]+]-sum[com[i]]<x) printf("-1\n");
else printf("%d\n",ask(,n,com[i],out[i]+,x));
}
return ;
}