题面

展开题面

题目描述

Black Box是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量i。最开始的时候Black Box是空的．而i等于0。这个Black Box要处理一串命令。

命令只有两种：

ADD(x):把x元素放进BlackBox;

GET:i加1，然后输出Blackhox中第i小的数。

记住：第i小的数，就是Black Box里的数的按从小到大的顺序排序后的第i个元素。例如：

我们来演示一下一个有11个命令的命令串。（如下图所示）

现在要求找出对于给定的命令串的最好的处理方法。ADD和GET命令分别最多200000个。现在用两个整数数组来表示命令串：

1.A(1)，A(2)，…A(M)：一串将要被放进Black Box的元素。每个数都是绝对值不超过2000000000的整数，M$200000。例如上面的例子就是A=(3，1，一4，2，8，-1000，2)。

2.u(1)，u(2)，…u(N)：表示第u(j)个元素被放进了Black Box里后就出现一个GET命令。例如上面的例子中u=(l，2，6，6)。输入数据不用判错。

输入输出格式

输入格式：

第一行，两个整数，M，N。

第二行，M个整数，表示A(l)…A(M)。

第三行，N个整数，表示u(l)…u(N)。

输出格式：

输出Black Box根据命令串所得出的输出串，一个数字一行。

思路

平衡树裸题，直接上板子。每次添加的时候 add ，查询的时候输出第 I 小的并更新 I 即可。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,y,l,r,size,cnt;
};
node s[1000001];
long long n,q,top=0;
long long root=0;
void update(long long x){
	s[x].size=s[s[x].l].size+s[s[x].r].size+s[x].cnt;
}
void rotr(long long &x){
	long long l=s[x].l;
	s[x].l=s[l].r;
	s[l].r=x;
	s[l].size=s[x].size;
	update(x);
	x=l;
}
void rotl(long long &x){
	long long r=s[x].r;
	s[x].r=s[r].l;
	s[r].l=x;
	s[r].size=s[x].size;
	update(x);
	x=r;
}
void add(long long &x,long long data){
	if (!x){
		x=++top;
		s[x].x=data;
		s[x].y=rand()%19260817;
		s[x].cnt=1;
		s[x].size=1;
		s[x].l=0;
		s[x].r=0;
		return;
	}
	s[x].size++;
	if (s[x].x==data){
		s[x].cnt++;
	}else if (data<s[x].x){
		add(s[x].l,data);
		if (s[x].y>s[s[x].l].y){
			rotr(x);
		}
	}else{
		add(s[x].r,data);
		if (s[x].y>s[s[x].r].y){
			rotl(x);
		}
	}
}
void del(long long &x,long long data){
	if (s[x].x==data){
		if (s[x].cnt>1){
			s[x].cnt--;
			s[x].size--;
			return;
		}
		if (!s[x].l||!s[x].r){
			x=s[x].l+s[x].r;
			return;
		}
		if (s[s[x].l].y<s[s[x].r].y){
			rotr(x);
			del(x,data);
		}else{
			rotl(x);
			del(x,data);
		}
		return;
	}
	s[x].size--;
	if (data<s[x].x){
		del(s[x].l,data);
	}else{
		del(s[x].r,data);
	}
}
long long pre(long long data){
	long long now=root,res=-2147483647;
	while (now){
		if (s[now].x<data){
			res=s[now].x;
			now=s[now].r;
		}else{
			now=s[now].l;
		}
	}
	return res;
}
long long nxt(long long data){
	long long now=root,res=2147483647;
	while (now){
		if (s[now].x>data){
			res=s[now].x;
			now=s[now].l;
		}else{
			now=s[now].r;
		}
	}
	return res;
}
long long querykth(long long k){
	long long now=root;
	while (now){
		if (s[s[now].l].size<k&&s[s[now].l].size+s[now].cnt>=k){
			return s[now].x;
		}
		if (s[s[now].l].size>=k){
			now=s[now].l;
		}else{
			k-=s[s[now].l].size+s[now].cnt;
			now=s[now].r;
		}
	}
	return 0;
}
long long queryrank(long long data){
	long long now=root,res=0;
	while (now){
		if (data==s[now].x){
			return res+s[s[now].l].size+1;
		}
		if (data<s[now].x){
			now=s[now].l;
		}else{
			res+=s[s[now].l].size+s[now].cnt;
			now=s[now].r;
		}
	}
	return res;
}
int a[1000000],b[1000000],I=0;
int m;
int main(){
	srand(time(0));
	cin>>q>>m;
	long long t,x;
	for (int i=1;i<=q;i++){
		cin>>a[i];
	}
	for (int i=1;i<=m;i++){
		cin>>b[i];
	}
	for (int i=1;i<=q;i++){
		add(root,a[i]);
		while (i==b[I+1]){
			I++;
			cout<<querykth(I)<<endl;
		}
	}
}