優先列二つの山のメンテナンス

1827 ワード

ニャンコ1073
説明
N個の数、M回のクエリーを入力します.
クエリーごとに数xが与えられます.
 
要求:毎回照会出力前のx個数のうち、i番目に小さい数.(iは第i回クエリー)
あなたはMを仮定することができます <= N,Xi<=Xi+1<=Xi+2<=….<=Xm(=N)
入力
Line 0:T
Line 1:N,M
Line 2…LineN+1:num 1、…、numN
Linen+2…LineN+2+M:x 1、…、xM
N<30000,num<20000000
出力
毎回照会出力前のiの小さい数は、単独の行です.
詳細なフォーマットはサンプルを参照してください.
サンプル入力
1
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
サンプル出力
3
3
1
2
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;


struct cmp{
	bool operator ()(int x,int y){
		return x>y;
	}
};
int main(){
	int T;
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		int a[n+1];
		for (int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		priority_queue<int> big;		//   ,top  i    
		priority_queue<int,vector<int>,cmp > small;	//    ,  i      
		int num;
		int count=1;
		int t;
		for (int i=1;i<=m;i++){
			scanf("%d",&num);
			while(count<=num){	//          num   
				if (big.size()<i){	//       i,   ,
							//        top ,    ,          ,          
							//                 
					if (small.size()==0) {
						big.push(a[count]);
						count++;
						continue;	
					}
					if (a[count]>small.top()){
						t=small.top();
						small.pop();
						small.push(a[count]);
						big.push(t);
					}
					else big.push(a[count]);
				}
				else {
					if (a[count]<big.top()){
						t=big.top();
						big.pop();
						big.push(a[count]);
						small.push(t);
					}
					else small.push(a[count]);	
				}
				count++;
			}
			if (big.size()<i){	//  big   i ,          
				t=small.top();
				small.pop();
				big.push(t);
			}
			cout<<big.top()<<endl;
		}
	} 
}