← 返回题目列表

Codeforces · 639/A

A. 熊和展示的朋友

中文机器翻译题面 查看原题

Limak 是一只小北极熊。他喜欢通过社交网络与其他熊联系。他有 n 个朋友,他与其中第 i 个朋友的关系由唯一的整数 ti 描述。这个值越大,友谊就越好。没有两个朋友具有相同的价值。

春天开始了,熊的冬眠结束了。 Limak 刚刚醒来并登录。他所有的朋友都还在睡觉,因此没有人在线。其中一些(也许全部)将在接下来的几个小时内一次一个地出现在网上。

系统显示在线好友。屏幕上最多可显示 k 个好友。如果有超过 k 个好友在线,那么系统将仅显示其中 k 个最好的好友 - 那些拥有最大 ti 的好友。

您的任务是处理两种类型的查询:

- “1 id”— 好友 ID 在线。可以保证他之前不在线。
- "2 id" — 检查系统是否显示好友id。在单独的行中打印“是”或“否”。

你能帮助 Limak 回答所有第二类问题吗?

输入

第一行包含三个整数n、k和q (1 ≤ n, q ≤ 150 000, 1 ≤ k ≤ min(6, n))——分别是好友数量、最大显示在线好友数量和查询数量。

第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 109),其中 ti 描述 Limak 与第 i 个朋友的关系有多好。

以下 q 行中的第 i 行包含两个整数 typei 和 idi (1 ≤ typei ≤ 2, 1 ≤ idi ≤ n) — 第 i 个查询。如果 typei = 1,则好友 idi 在线。如果 typei = 2 那么你应该检查是否显示好友 idi。

保证第一种类型的两个查询不会具有相同的 idi,因为一个朋友不能两次在线。此外,还保证至少一个查询属于第二种类型 (typei = 2),因此输出不会为空。

输出

对于第二种类型的每个查询,打印一行包含答案 - 如果显示给定的朋友,则打印“是”(不带引号),否则打印“否”(不带引号)。

示例

输入 #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

注意

在第一个样本中,Limak 有 4 个朋友,他们最初都在睡觉。一开始,系统显示没有人,因为没有人在线。有以下8个查询:

1.“1 3”— 好友 3 上线。
2.“2 4”—我们应该检查是否显示了好友 4。他甚至不在线,因此我们打印“NO”。
3.“2 3”—我们应该检查是否显示了好友 3。目前他是唯一在线好友,系统会显示他。我们应该打印“YES”。
4.“1 1”— 好友 1 上线。系统现在同时显示好友 1 和好友 3。
5.“1 2”— 好友 2 上线。现在有 3 个好友在线,但我们给出了 k = 2,所以只能显示两个好友。 Limak 与好友 1 的关系比与其他两个在线好友的关系更差 (t1 < t2, t3),因此好友 1 不会显示
6.“2 1”—打印“否”。
7.“2 2”—打印“是”。
8.“2 3”—打印“是”。