FHQ 20pts 求条玄关
查看原帖
FHQ 20pts 求条玄关
1367000
Ybll_楼主2025/6/17 14:26
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct PII
{
	int first;
	string second;
	bool operator >=(const PII &ljh)const
	{
		return (first==ljh.first?(second<=ljh.second):(first>=ljh.first));
	}
};
struct FHQ_Treap
{
	struct fhq_treap
	{
		int sz,l,r,fix;
		PII val;
	}tree[N*10];
	int T,cnt,p,a,root;
	int new_node(int x,string y)
	{
	    tree[++cnt].sz=1;
	    tree[cnt].val={x,y};
	    tree[cnt].fix=rand();
	    return cnt;
	}
	void push_up(int x)
	{
		tree[x].sz=1+tree[tree[x].l].sz+tree[tree[x].r].sz;
	}
	void split(int now, PII k,int &x,int &y)
	{
	    if(!now)x=y=0;
	    else
		{
	        if(tree[now].val>=k)
	        {
	        	x=now;
				split(tree[now].r,k,tree[x].r,y);
			}
	        else
	        {
	        	y=now;
				split(tree[now].l,k,x,tree[y].l);
			}
	        push_up(now); 
	    }
	}
	int merge(int x,int y)
	{
	    if(!x||!y)return x+y;
	    if(tree[x].fix<tree[y].fix)
	    {
	    	tree[x].r=merge(tree[x].r,y);
	    	push_up(x);
	    	return x;
		}
		tree[y].l=merge(x,tree[y].l);
		push_up(y);
	    return y;
	}	
	PII kth(int now,int rank)
	{
	    if(tree[tree[now].l].sz+1==rank)return tree[now].val;
	    if(rank<=tree[tree[now].l].sz)return kth(tree[now].l,rank);
	    return kth(tree[now].r,rank-tree[tree[now].l].sz-1);
	}
}FHQ;
struct Trie_Tree
{
	int tree[N*10][26],cnt=0,root[N*10],x,y,z;
	void insert(string s)
	{
		int now=0;
		for(int i=0,j;i<s.size();i++)
		{
			j=s[i]-'a';
			if(!tree[now][j])
			{
				tree[now][j]=++cnt;
				root[tree[now][j]]=FHQ.new_node(0,s);
			}
			else
			{
				FHQ.split(root[tree[now][j]],{0,s},x,y);
				root[tree[now][j]]=FHQ.merge(FHQ.merge(x,FHQ.new_node(0,s)),y);
			}
			now=tree[now][j];
		}
	}
	void find(string s,int x)
	{
		int now=0;
		for(int i=0,j;i<s.size();i++)
		{
			j=s[i]-'a';
			if(!tree[now][j])
			{
				cout<<"404Error\n";
				return;
			}
			now=tree[now][j];
		}
		x=min(FHQ.tree[root[now]].sz,x);
		PII p=FHQ.kth(root[now],x);
		string q=p.second;
		cout<<q<<"\n";
		q[q.size()-1]--;
		now=0;
		for(int i=0,j;i<p.second.size();i++)
		{
			j=p.second[i]-'a';
			now=tree[now][j];
			FHQ.split(root[now],{p.first,q},x,z);
			FHQ.split(z,p,y,z);
			root[now]=FHQ.merge(x,z);
			FHQ.tree[y].val={p.first+1,p.second};
			FHQ.split(root[now],FHQ.tree[y].val,x,z);
			root[now]=FHQ.merge(FHQ.merge(x,y),z);
		}
	}
}trie;
signed main()
{
	int n,Q;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		trie.insert(s);
	}
	cin>>Q;
	while(Q--)
	{
		int x;
		string s;
		cin>>s>>x;
		trie.find(s,x);
	}
	return 0;
}
2025/6/17 14:26
加载中...