luoguP3850题解

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;
const int maxn=1e5+205;

struct FHQ_Node
{
	int ch[2],siz,rnd;
	string val;
}tr[maxn];
int utot;

inline int newnode(string val) {tr[++utot].rnd=rand();tr[utot].siz=1;tr[utot].val=val;return utot;}

inline void update(int u) {tr[u].siz=tr[tr[u].ch[0]].siz+tr[tr[u].ch[1]].siz+1;}

inline void split(int u,int siz,int &x,int &y)
{
	if(!u) return void(x=y=0);
	if(tr[tr[u].ch[0]].siz>=siz) y=u,split(tr[u].ch[0],siz,x,tr[u].ch[0]);//左儿子的size+1表示它在区间中的排名
	else x=u,split(tr[u].ch[1],siz-tr[tr[u].ch[0]].siz-1,tr[u].ch[1],y);
	update(u);
}

inline int merge(int x,int y)
{
	if(!x||!y) return x|y;
	if(tr[x].rnd<tr[y].rnd)
	{
		tr[x].ch[1]=merge(tr[x].ch[1],y);update(x);return x;
	}
	else
	{
		tr[y].ch[0]=merge(x,tr[y].ch[0]);update(y);return y;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	srand(time(0));
	int n,rt=0,r1=0,r2=0,x,m,q;
	string s;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		rt=merge(rt,newnode(s));
	}
	cin>>m;
	while(m--)
	{
		cin>>s>>x;
		split(rt,x,rt,r1);
		rt=merge(rt,merge(newnode(s),r1));
	}
	cin>>q;
	while(q--)
	{
		cin>>x;
		split(rt,x+1,rt,r1);
		split(rt,x,rt,r2);
		cout<<tr[r2].val<<endl;
		rt=merge(rt,merge(r2,r1));
	}
	return 0;
}