记录编号	245246	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.049 s
提交时间	2016-04-02 17:47:03	内存使用	1.23 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int I=0,rt=0,cnt;
struct PoPoQQQ
{
	struct u
	{
		int f;
		int s;
		int z;
		int d;
		int e[2];
	}c[30010];
	/*void gts()
	{
		printf("%d\n",rt);
		for(int i=1;i<=cnt;i++)
		    printf("%d %d %d %d %d %d\n",c[i].f,c[i].e[0],c[i].e[1],c[i].z,c[i].d,c[i].s);
	}*/
	void Update(int a)
	{
		c[a].s=c[c[a].e[0]].s+c[c[a].e[1]].s+c[a].d;
	}
	void gy(int a)
	{
		int x=c[a].f;
		int o=c[x].f;
		c[a].f=c[x].f;
		c[x].e[0]=c[a].e[1];
		c[c[a].e[1]].f=x;
		c[x].f=a;
		c[a].e[1]=x;
		if(o)
		{
			if(c[o].e[0]==x)
			    c[o].e[0]=a;
			else
			    c[o].e[1]=a;
		}
		Update(x);
		Update(a);
	}
	void gz(int a)
	{
		int x=c[a].f;
		int o=c[x].f;
		c[a].f=c[x].f;
		c[x].e[1]=c[a].e[0];
		c[c[a].e[0]].f=x;
		c[x].f=a;
		c[a].e[0]=x;
		if(o)
		{
			if(c[o].e[0]==x)
			    c[o].e[0]=a;
			else
			    c[o].e[1]=a;
		}
		Update(x);
		Update(a);
	}
	void Splay(int a)
	{
		//puts("----------------------------------");
		//gts();
		while(c[a].f!=0)
		{
			int x=c[a].f;
			if(c[x].e[0]==a)
			    gy(a);
			else
			    gz(a);
		}
		rt=a;
		//gts();
		//puts("----------------------------------");
	}
	void Insert(int a)
	{
		int k=rt;
		int fa=0;
		while(k)
		{
			fa=k;
			if(c[k].z==a)
			{
				c[k].s++;
				c[k].d++;
				Splay(k);
				return;
			}
			if(c[k].z<a)
			    k=c[k].e[1];
			else
			    k=c[k].e[0];
		}
		++cnt;
		c[cnt].z=a;
		c[cnt].d=c[cnt].s=1;
		if(fa==0)
		    rt=cnt;
		else
		{
			c[cnt].f=fa;
			if(c[fa].z<a)
			    c[fa].e[1]=cnt;
			else
			    c[fa].e[0]=cnt;
			Splay(cnt);
		}
	}
	void gw()
	{
		++I;
		int o=I;
		//printf("G%d\n",o);
		int p=rt;
		while(1)
		{
			//printf("H");
			if(c[c[p].e[0]].s>=o)
			    p=c[p].e[0];
			else if(c[c[p].e[0]].s+c[p].d>=o)
			{
				printf("%d\n",c[p].z);
				return;
			}
			else
			{
				o-=c[c[p].e[0]].s+c[p].d;
				p=c[p].e[1];
			}
		}
	}
}splay;
int n,m,A[30010],u[30010];
int main()
{
	freopen("blackbox.in","r",stdin);
	freopen("blackbox.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	    scanf("%d",&A[i]);
	for(int i=1;i<=m;i++)
	    scanf("%d",&u[i]);
	int l=1;
	for(int i=1;i<=n;i++)
	{
		splay.Insert(A[i]);
		//printf("I%d ",i);
		while(l<=m&&u[l]==i)
		{
			//printf("L");
			splay.gw();
			++l;
		}
	}
	getchar();
	getchar();
}