求助fhq
查看原帖
求助fhq
264548
Tangent233楼主2021/10/16 16:05

全wa了不知道为什么,也看不到数据

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
struct node
{
	int l,r;
	string val;
	int key,sz;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define v(x) tree[x].val
	#define k(x) tree[x].key
	#define s(x) tree[x].sz
}tree[maxn];
int rt,now,x,y,z;
int newnode(string a)
{
	v(++now)=a;
	k(now)=rand();
	s(now)=1;
	return now;
}
void update(int x)
{
	s(x)=s(l(x))+s(r(x))+1;
}
void split(int now,int siz,int &x,int &y)
{
	if(!now) x=y=0;
	else
	{
		if(s(l(now))<siz)
		{
			x=now;
			split(r(now),siz-s(l(now))-1,r(now),y);
		}
		else
		{
			y=now;
			split(l(now),siz,x,l(now));
		}
		update(now);
	}
}
int merge1(int x,int y)
{
	if(!x||!y) return x+y;
	if(k(x)<k(y))
	{
		r(x)=merge1(r(x),y);
		update(x);
		return x;
	}
	else
	{
		l(y)=merge1(x,l(y));
		update(y);
		return y;
	}
}
void addbook(string a,int p)
{
	int k=newnode(a);
	if(p==1)
	{
		merge1(k,rt);
		return;
	}
	split(rt,p-1,x,y);
	merge1(merge1(x,k),y);
}
void askbook(int p)
{
	split(rt,p-1,x,y);
	split(y,1,y,z);
	cout<<v(y)<<endl;
	merge1(merge1(x,y),z);
}
string ppp;
int main()
{
	srand(114514);
	int n,m,q,v;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>ppp;
		rt=merge1(rt,newnode(ppp));
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>ppp>>v;
		addbook(ppp,v+1);
	}
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>v;
		askbook(v+1);
	}
	return 0;
}
2021/10/16 16:05
加载中...