自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

搬运于2025-08-24 22:30:13，当前版本为作者最后更新于2020-12-28 20:48:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

19 年就对着自己的输入法出出来的一道题，当初觉得好难，要 n 重数据结构，现在看起来。。。。。。
还是先来看部分分吧。

10pts

建一棵 Trie，暴力维护子树最大值，或者干脆 Trie 都不建直接查。

20pts

建一棵 Trie，暴力将其值排序，然后更新答案。

30pts

发现最大值只增不减，所以每一个 Trie 的节点上只用记录最大值和那个字符串，每次子树内有东西发生更新就来更新一下自己的最大值，由于 Trie 层数小于等于10，所以复杂度 $O(n)$，是正确的。

50~95 pts

防止常数过大者变成暴力分。

100pts

考虑正解。肯定要把字符串集合建成一棵 Trie。它的后缀就相当于 Trie 节点的子树。首先，我们在每一个 Trie 节点开一棵平衡树存入子树内的值和字符串，这样就很方便的维护子树 kth。
每一次，我们找到了一个对应的字符串，就去所有它的前缀去更新它的值，以便下一次更新。
如果 Trie 节点不存在，直接输出 404Error。
总的时间复杂度为 $O(nlogn)$。
代码如下，写的是标准 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 序上查询区间第 $k$ 大，时间复杂度 $O(nlog^2n)\sim O(nlog^3n)$。