题目
Description
Limak is a little polar bear. He loves connecting with other bears via social networks. He has n friends and his relation with the i-th of them is described by a unique integer ti. The bigger this value is, the better the friendship is. No two friends have the same value ti.
Spring is starting and the Winter sleep is over for bears. Limak has just woken up and logged in. All his friends still sleep and thus none of them is online. Some (maybe all) of them will appear online in the next hours, one at a time.
The system displays friends who are online. On the screen there is space to display at most k friends. If there are more than k friends online then the system displays only k best of them — those with biggest ti.
Your task is to handle queries of two types:
"1 id" — Friend id becomes online. It's guaranteed that he wasn't online before.
"2 id" — Check whether friend id is displayed by the system. Print "YES" or "NO" in a separate line.
Are you able to help Limak and answer all queries of the second type?Input
The first line contains three integers n, k and q (1 ≤ n, q ≤ 150000, 1 ≤ k ≤ min(6, n)) — the number of friends, the maximum number of displayed online friends and the number of queries, respectively.
The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 109) where ti describes how good is Limak's relation with the i-th friend.
The i-th of the following q lines contains two integers typei and idi (1 ≤ typei ≤ 2, 1 ≤ idi ≤ n) — the i-th query. If typei = 1 then a friend idi becomes online. If typei = 2 then you should check whether a friend idi is displayed.
It's guaranteed that no two queries of the first type will have the same idi becuase one friend can't become online twice. Also, it's guaranteed that at least one query will be of the second type (typei = 2) so the ## Output won't be empty.
Output
For each query of the second type print one line with the answer — "YES" (without quotes) if the given friend is displayed and "NO" (without quotes) otherwise.Sample Input
Input
4 2 8
300 950 500 200
1 3
2 4
2 3
1 1
1 2
2 1
2 2
2 3Output
NO
YES
NO
YES
YESInput
6 3 9
50 20 51 17 99 24
1 3
1 4
1 5
1 2
2 4
2 2
1 1
2 4
2 3Output
NO
YES
NO
YES
题解
题目大致意思就是查询好友是否在线
如果好友超过限制,则下线友情度较低的好友
使用优先队列维护在线好友,如果超过限制就将好友出队
由于优先队列不能使用迭代器,因此额外维护一个布尔数组记录编号为 i
的好友是否在队列中
代码
/* By:OhYee Github:OhYee Blog:http://www.oyohyee.com/ Email:oyohyee@oyohyee.com かしこいかわいい? エリーチカ! 要写出来Хорошо的代码哦~ */ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> #include <functional> using namespace std; const int maxn = 150005; int weight[maxn]; struct Node { int n; Node(int a) { n = a; } bool operator < (const Node &rhs)const { return weight[n] > weight[rhs.n]; } }; priority_queue<Node> Q; bool flag[maxn]; void init() { memset(flag,false,sizeof(flag)); while(!Q.empty()) Q.pop(); } bool Do() { int n,k,q; if(scanf("%d%d%d",&n,&k,&q)==EOF) return false; init(); for(int i = 1;i <= n;i++) scanf("%d",&weight[i]); for(int i = 0;i < q;i++) { int com; scanf("%d",&com); if(com == 1) { int t; scanf("%d",&t); flag[t] = true; Q.push(Node(t)); while((int)Q.size() > k) { flag[Q.top().n] = false; Q.pop(); } } else { int t; scanf("%d",&t); if(flag[t]) printf("YES\n"); else printf("NO\n"); } } //printf("\n"); return true; } int main() { while(Do()); return 0; }