【NOIP模拟赛】点名

2014年11月2日1,3690

【题目描述】

J班的体育课上,同学们常常会迟到几分钟,但体育老师的点名却一直很准时。老师只关心同学的身高,他会依次询问当前最矮的身高,次矮的身高,第三矮的身高,等等。在询问的过程中,会不时地有人插进队伍里。你需要回答老师每次的询问。

【输入格式】

第一行两个整数n m,表示先后有n个人进队,老师询问了m

第二行n个整数,第i个数Ai表示第i个进入队伍的同学的身高为Ai

第三行m个整数,第j个数Bj表示老师在第Bj个同学进入队伍后有一次询问

【输出格式】

m行,每行一个整数,依次表示老师每次询问的答案。数据保证合法

【样例输入】

7 4

97281418

1 2 6 6

【样例输出】

9

9

7

8

【样例解释】

(9){No.1 = 9}; (9 7){No.2 = 9}; (9 7 2 8 14 1){No.3 = 7; No.4 = 8}

【数据范围】

40%的数据保证n≤1000

100%的数据保证1≤m≤n≤30000;0≤Ai<2^32

题解

此题坑点在于,会爆int。。

然后裸的平衡树就能水过啦,插入,查K小

题解写了个离散+树状数组是要二分么不解。。

离线+并查集/链表。。。好吧这个无语了

我写了个pq的2333,这个很短

维护前K大的大根堆 A

维护其余的小根堆 B

插入:A.insert() B.insert(A.pop())

询问:ans = A.top(); A.insert(B.pop())