题解--简易输入法
19 年就对着自己的输入法出出来的一道题，当初觉得好难，要 n 重数据结构，现在看起来。。。。。。
还是先来看部分分吧。
10pts
建一棵 Trie，暴力维护子树最大值，或者干脆 Trie 都不建直接查。
20pts
建一棵 Trie，暴力将其值排序，然后更新答案。
30pts
发现最大值只增不减，所以每一个 Trie 的节点上只用记录最大值和那个字符串，每次子树内有东西发生更新就来更新一下自己的最大值，由于 Trie 层数小于等于10，所以复杂度
50~95 pts
防止常数过大者变成暴力分。
100pts
考虑正解。肯定要把字符串集合建成一棵 Trie。它的后缀就相当于 Trie 节点的子树。首先，我们在每一个 Trie 节点开一棵平衡树存入子树内的值和字符串，这样就很方便的维护子树 kth。
每一次，我们找到了一个对应的字符串，就去所有它的前缀去更新它的值，以便下一次更新。
如果 Trie 节点不存在，直接输出 404Error。
总的时间复杂度为
代码如下，写的是标准 Trie 套 Splay，有亿点点长。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m;
struct splaytree {
int news,cnt;
splaytree() {
cnt=0;
}
struct tree {
int sum,f,siz,ch[2];
string s;
} t[maxn*10];
void pushup(int x) {
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
return;
}
void rotate(int x,int &rot) {
int y=t[x].f,z=t[y].f,L=(t[y].ch[0]!=x),R=L^1;
if(y==rot) {
rot=x;
} else {
t[z].ch[t[z].ch[0]!=y]=x;
}
t[x].f=z;
t[y].f=x;
t[t[x].ch[R]].f=y;
t[y].ch[L]=t[x].ch[R];
t[x].ch[R]=y;
pushup(y);
pushup(x);
}
void splay(int x,int &rot) {
while(x!=rot) {
int y=t[x].f,z=t[y].f;
if(y!=rot) {
if(t[y].ch[0]==x^t[z].ch[0]==y) {
rotate(x,rot);
} else {
rotate(y,rot);
}
}
rotate(x,rot);
}
}
void insert(int rot,int x,string s) {
if((t[rot].sum<x||(t[rot].sum==x&&t[rot].s>s))&&t[rot].ch[0]) {
insert(t[rot].ch[0],x,s);
} else if((t[rot].sum>x||(t[rot].sum==x&&t[rot].s<s))&&t[rot].ch[1]) {
insert(t[rot].ch[1],x,s);
} else {
t[rot].ch[t[rot].sum>x|(t[rot].sum==x&t[rot].s<s)]=++cnt;//注意这里值是从大到小排，符号不要写反，先后顺序不要弄错
t[cnt].f=rot;
t[cnt].siz=1;
t[cnt].sum=x;
t[cnt].s=s;
news=cnt;
}
pushup(rot);
}
int getfront(int rot) {
int x=t[rot].ch[0];
while(t[x].ch[1]) {
x=t[x].ch[1];
}
return x;
}
int getback(int rot) {
int x=t[rot].ch[1];
while(t[x].ch[0]) {
x=t[x].ch[0];
}
return x;
}
void del(int &root,int rot,int x,string s) {
if((t[rot].sum<x||(t[rot].sum==x&&t[rot].s>s))&&t[rot].ch[0]) {
del(root,t[rot].ch[0],x,s);
} else if((t[rot].sum>x||(t[rot].sum==x&&t[rot].s<s))&&t[rot].ch[1]) {
del(root,t[rot].ch[1],x,s);//删除的时候也一样
} else {
splay(rot,root);
int he=getfront(root),ta=getback(root);
splay(he,root);
splay(ta,t[he].ch[1]);
t[rot].f=t[rot].siz=t[rot].sum=t[ta].ch[0]=0;
t[rot].s="";
pushup(ta);
pushup(he);
}
pushup(rot);
}
int findx(int &rot,int x,string s) {
if(!rot)return 0;
int u=rot;
while(t[u].ch[t[u].sum>x|(t[u].sum==x&t[u].s<s)]&&t[u].sum!=x&&t[u].s!=s) {
u=t[u].ch[t[u].sum>x|(t[u].sum==x&t[u].s<s)];//这里可能有点丑，意义是从根找到它那一棵子树
}
splay(u,rot);
return t[t[rot].ch[0]].siz-1;
}
int findk(int rot,int k) {
int lsiz=t[t[rot].ch[0]].siz;
if(!rot)return 0;
if(lsiz==k-1) {
return rot;
} else if(lsiz>=k) {
return findk(t[rot].ch[0],k);
} else {
return findk(t[rot].ch[1],k-lsiz-1);
}
}
void tab(int &root) {
root=++cnt;
cnt++;//这里如果写t[++cnt].f=cnt-1;会有UB
t[cnt].f=cnt-1;
t[cnt-1].ch[0]=cnt;
t[cnt].sum=INT_MAX;
t[cnt-1].sum=INT_MIN+1;//初始化时值的顺序不要弄反
t[cnt].siz=1;
t[cnt-1].siz=2;
t[cnt].s="";
}
} Splay;
struct Trietree {
int t[maxn*3][26],cnt,rt[maxn*3];
Trietree() {
cnt=0;
}
void insert(string s) {
int root=0,y;
for(register int i=0; i<s.length(); i++) {
y=s[i]-'a';
if(!t[root][y]) {
t[root][y]=++cnt;
Splay.tab(rt[cnt]);
}
root=t[root][y];
Splay.insert(rt[root],0,s);
}
}
string ask(string s,int k) {
int root=0,y;
for(register int i=0; i<s.length(); i++) {
y=s[i]-'a';
if(!t[root][y]) {
return "404Error";
}
root=t[root][y];
}
k=min(k,Splay.t[rt[root]].siz-2);//处理第二种情况，先取一个min，注意是siz-2
int w=Splay.findk(rt[root],k+1),p=Splay.t[w].sum+1;
string astr=Splay.t[w].s;//astr和p是找到的字符串的值
root=0;
for(register int i=0; i<astr.length(); i++) {
y=astr[i]-'a';
root=t[root][y];
Splay.del(rt[root],rt[root],p-1,astr);//注意删除是删值为p-1
Splay.insert(rt[root],p,astr);
Splay.splay(Splay.news,rt[root]);
}
return astr;
}
} Trie;
char str[10];
int main() {
int x;
string s1;
scanf("%d",&n);
for(register int i=1; i<=n; i++) {
scanf("%s",str);
s1=str;
Trie.insert(s1);
}
scanf("%d",&m);
for(register int i=1; i<=m; i++) {
scanf("%s%d",str,&x);
s1=str;
cout<<Trie.ask(s1,x);
}
return 0;
}当然，你也可以通过 DFS 序把 Trie 拍扁，然后在 dfn 序上查询区间第