1.题面

传送门

2.解题思路

解题思路1-双优先队列解法

这是我第二次见到有人使用treap求解第K大值了，看来有必要学习一下treap了。这道题我是使用两个堆做的，解这道题目我们需要维护两个堆，一个大顶堆，一个小顶堆，只需要这两个堆满足以下三个条件：

??????? 1.大顶堆和小顶堆的元素并为全集

??????? 2.大顶堆和小顶堆中没有重叠元素（这个重叠不太好说，我们先假设所有的元素都是不一样的，这样比较容易理解）

??????? 3.大顶堆的堆顶要小于小顶堆的堆顶

??????? 4.大顶堆的size是k

在这样的情况下，我们可以说大顶堆的堆顶是整个集合中的第K个元素。

证明应该不需要多说，可以理解小顶堆中所有的元素都比大顶堆的堆顶要大，大顶堆中所有的元素除了堆顶，都比堆顶元素要小，自然大顶堆堆顶就是第K大的元素了。

为了实现这样的条件来查找第K大的值，我们只需要两步

第一步：调整大顶堆元素为K，当大顶堆元素不足K时，从小顶堆中弹出元素压入大顶堆中；当大顶堆中元素大于K时，从大顶堆中弹出元素放入小顶堆中

第二步：调整大顶堆堆顶小于小顶堆堆顶。当大顶堆堆顶大于小顶堆堆顶时，分别弹出两个堆顶元素，并压入另一个堆中。

然后就OK啦

事实上这样的调整复杂度还是O（nlogn），但常数要小很多，最终还过了。然后在使用STL的时候要时时刻刻记得查看stack，queue，priority_queue是不是空的，经常为因为忘记这个出错。

解题思路2-Treap求第K小值

表示Treap是我见过的平衡树中最容易实现的了，插入只有两种旋转方式，删除时如果采用将孩子节点中较小的孩子旋转上来的话，也很容易实现。如果输入数据有多组也许要清理一下之前分配的内存，因为这道题只有一组数据，所以不清理也是可以的，而且更重要的原因是，清理消耗时间比较多，而竞赛中对于时间的限制要远远比对于空间的限制严格。我尝试了一下清理数据，发现慢了几十毫秒，应该是是可以承受的。

最终，查找第K小值的时候，你只需要根据左子树中元素的个数，以及自身元素重复的次数，就可以确定你应当到右子树中去搜索还是去左子树中搜索，还是你已经找到了答案。个人感觉这个函数能比较简单地写成while循环，有时间我去改改。

PS：我写的代码是支持重复元素的插入删除与查找K值的，但是这道题并没有说是否存在重复元素，所以虽然AC了，还不能确定这个功能是完全正确的。

3.解题代码

解题代码1-双优先队列

/*****************************************************************
    > File Name: tmp.cpp
    > Author: Uncle_Sugar
    > Mail: uncle_sugar@qq.com
    > Created Time: 2016年02月24日 星期三 18时44分40秒
 ****************************************************************/
# include <cstdio>
# include <cstring>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;

const int debug = 1;
const int size  = 100000 + 10; 
typedef long long ll;

ll add[size],get[size];
int main()
{
	std::ios::sync_with_stdio(false);cin.tie(0);
	int i,j,k;
	int n,m;
	priority_queue<ll,vector<ll>,greater<ll> > minheap;
	priority_queue<ll,less<ll> > maxheap;
	ll tmp;
	while (cin >> m >> n){
		while (!minheap.empty())	minheap.pop();
		while (!minheap.empty())	maxheap.pop();
		for (i=1;i<=m;i++){
			cin >> add[i];
		}
		for (i=1;i<=n;i++){
			cin >> get[i];
		}
		k = 1;
		for (i=1;i<=n;i++){
			for (;k<=get[i];k++){
				minheap.push(add[k]);
			}
			int s = k-1;
			while (maxheap.size()>i){
				minheap.push(maxheap.top());
				maxheap.pop();
			}
			while (maxheap.size()<i){
				maxheap.push(minheap.top());
				minheap.pop();
			}
			if (!minheap.empty()&&!maxheap.empty())
				while (minheap.top()<maxheap.top()){
					ll t1 = maxheap.top();maxheap.pop();
					ll t2 = minheap.top();minheap.pop();
					minheap.push(t1);
					maxheap.push(t2);
				}
			cout << maxheap.top() << 'n';
		}
	}
	return 0;
}

解题代码2-Treap查找第K大值

/*****************************************************************
    > File Name: tmp.cpp
    > Author: Uncle_Sugar
    > Mail: uncle_sugar@qq.com
    > Created Time: 2016年02月27日 星期六 17时20分14秒
*****************************************************************/
# include <cstdio>
# include <cstring>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;

const int debug = 0;
const int size  = 1000000 + 10;
typedef long long ll;

# ifndef ONLINE_JUDGE
struct DesktopIO{
	DesktopIO(){
		freopen("//home//unclesugar//in.txt","r",stdin);
		freopen("//home//unclesugar//out.txt","w",stdout);
	}
}DIO;
# endif

struct Treap_Node{
	int value;
	int fix,cnt,size;
	Treap_Node *left,*right;
	Treap_Node():cnt(0),size(0),left(NULL),right(NULL){}
	Treap_Node(int _value):value(_value),cnt(0),right(NULL){}
}*root = NULL;
inline void Treap_SetSize(Treap_Node *&P){
	if (P){
		P->size = P->cnt;
		if (P->left)	P->size += P->left->size;
		if (P->right)	P->size += P->right->size;
	}
}
inline int lsize(Treap_Node *&P){
	return P->left?P->left->size:0;
}
inline int rsize(Treap_Node *&P){
	return P->right?P->right->size:0;
}
void Treap_Left_Rotate(Treap_Node *&a){
	Treap_Node *b = a->right;
	a->right = b->left;
	b->left = a;
	a = b;
	Treap_SetSize(a->left);
	Treap_SetSize(a->right);
	Treap_SetSize(a);
}
void Treap_Right_Rotate(Treap_Node *&a){
	Treap_Node *b = a->left;
	a->left = b->right;
	b->right = a;
	a = b;
	Treap_SetSize(a->left);
	Treap_SetSize(a->right);
	Treap_SetSize(a);
}
void Treap_Insert(Treap_Node *&P,int value){
	if (!P){
		P = new Treap_Node;
		P->value = value;
		P->fix = rand();
	}
	if (value < P->value){
		Treap_Insert(P->left,value);
		if (P->left->fix < P->fix)
			Treap_Right_Rotate(P);
	}
	else if (P->value < value){
		Treap_Insert(P->right,value);
		if (P->right->fix < P->fix)
			Treap_Left_Rotate(P);
	}
	else {
		P->cnt++;
	}
	Treap_SetSize(P);
}
Treap_Node* Treap_Findkth(Treap_Node *&P,int k){
	if (k <= lsize(P))
		return Treap_Findkth(P->left,k);
	else if (k > lsize(P)+P->cnt)
		return Treap_Findkth(P->right,k-(lsize(P)+P->cnt));
	else
		return P;
}
void Treap_Clear(Treap_Node *&root){
	if (root->left)
		Treap_Clear(root->left);
	if (root->right)
		Treap_Clear(root->right);
	delete root;
	root = NULL;
}

int data[size];
int query[size];
int main()
{
	std::ios::sync_with_stdio(false);cin.tie(0);
	int i,k,tmp;
	int n,m;
	while (cin >> n >> m){
		for (i=0;i<n;i++)
			cin >> data[i];
		for (i=0;i<m;i++)
			cin >> query[i];
		for (k=i=0;i<m;i++){
			while (k<query[i]){
				Treap_Insert(root,data[k]);
				k++;
			}
			Treap_Node *T = Treap_Findkth(root,i+1);
			cout << T->value << 'n';
		}
		Treap_Clear(root);
	}
	return 0;
}