Bear and Displayed Friends

题意翻译

# 题目表述 Limak有n个朋友，他与第i个朋友的友谊值是ti，题目保证不会出现两个朋友的友谊值相同。 有一天，Limak上网和朋友聊天，此时只有Limak在线，接下来，会有一些朋友陆续上线。 系统会显示在线的朋友，但如果超过k个，系统只会显示ti最大的k个。 你的任务是处理两种查讯: “1 id”表示id号的朋友上线，保证他以前没有在线； “2 id”检测系统会不会显示id号的朋友，在单独一行中输出“YES”或“NO”。 # 输入格式 第1行，n、k、q (1<=n,q<=150000,1<=k<=min(6,n)1<=n,q<=150000,1<=k<=min(6,n) )，n和k如题，q表示询问的次数。 第2行，n个数，第i个数表示 id为i的人的友谊值。 接下来q行，表示q次询问，每行两个数分别是type，id(1<=type<=2,1<=id<=n) # 输出格式 对于每个type=2的询问，如果系统会显示这个人，在单独的一行中输出“YES”，否则输出“NO”。

题目描述

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 $ t_{i} $ . The bigger this value is, the better the friendship is. No two friends have the same value $ t_{i} $ . 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 $ t_{i} $ . 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?

输入输出格式

输入格式

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 $ t_{1},t_{2},...,t_{n} $ ( $ 1<=t_{i}<=10^{9} $ ) where $ t_{i} $ describes how good is Limak's relation with the $ i $ -th friend. The $ i $ -th of the following $ q $ lines contains two integers $ type_{i} $ and $ id_{i} $ ( $ 1<=type_{i}<=2,1<=id_{i}<=n $ ) — the $ i $ -th query. If $ type_{i}=1 $ then a friend $ id_{i} $ becomes online. If $ type_{i}=2 $ then you should check whether a friend $ id_{i} $ is displayed. It's guaranteed that no two queries of the first type will have the same $ id_{i} $ becuase one friend can't become online twice. Also, it's guaranteed that at least one query will be of the second type ( $ type_{i}=2 $ ) so the output won't be empty.

输出格式

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.

输入输出样例

输入样例 #1

4 2 8
300 950 500 200
1 3
2 4
2 3
1 1
1 2
2 1
2 2
2 3

输出样例 #1

NO
YES
NO
YES
YES

输入样例 #2

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 3

输出样例 #2

NO
YES
NO
YES

说明

In the first sample, Limak has $ 4 $ friends who all sleep initially. At first, the system displays nobody because nobody is online. There are the following $ 8 $ queries: 1. "1 3" — Friend $ 3 $ becomes online. 2. "2 4" — We should check if friend $ 4 $ is displayed. He isn't even online and thus we print "NO". 3. "2 3" — We should check if friend $ 3 $ is displayed. Right now he is the only friend online and the system displays him. We should print "YES". 4. "1 1" — Friend $ 1 $ becomes online. The system now displays both friend $ 1 $ and friend $ 3 $ . 5. "1 2" — Friend $ 2 $ becomes online. There are $ 3 $ friends online now but we were given $ k=2 $ so only two friends can be displayed. Limak has worse relation with friend $ 1 $ than with other two online friends ( $ t_{1}&lt;t_{2},t_{3} $ ) so friend $ 1 $ won't be displayed 6. "2 1" — Print "NO". 7. "2 2" — Print "YES". 8. "2 3" — Print "YES".