Performance Review

题意翻译

### 题意 一个公司有 n 个员工，每个员工有一个能力值 $a_i$， 每个 $a_i$ 都不一样。公司采取末位淘汰制，我们考虑 m 年，每年年底都会补充 $r_i$ 个新员工，每个新员工的能力值被表示为 $b_{i_j}$, 即第 $i$ 年新加入的第 $j$ 个员工的能力值。每年，能力值最靠后的 $r_i$ 个员工会被炒鱿鱼，取而代之的是新加入的这 $r_i$ 个员工。你是第 1 号员工，你的能力值是 $a_1$ 。 还有 $q$ 次操作，每次操作的描述形如 $(x_i,y_i,z_i)$， 表示把第 $x_i$ 年加入的第 $y_i$ 个员工的能力值改为 $z_i$。 现在对于每个操作输出 $0$ 或 $1$，表示如果进行完这个操作，$m$ 年之后你会不会被炒鱿鱼。注意，操作是永久性的。 ### 输入格式 第一行三个正整数 $n,m,q$，$2\le n\le 10^5,\ \ 1\le m,q\le 10^5$。 之后的 $m$ 行，每行描述一年新加入的员工的信息。每行第一个整数是 $r_i$, 表示今年新加入的员工数量，之后的 $r_i$ 个正整数，描述员工能力值。之后的 $q$ 行，每行描述一个操作。 ### 输出格式 共 $q$ 行，对于每个操作输出 $0$ 或 $1$。

题目描述

Randall is a software engineer at a company with $ N $ employees. Every year, the company re-evaluates its employees. At the end of every year, the company replaces its several worst-performing employees and replaces with the same number of new employees, so that the company keeps having $ N $ employees. Each person has a constant performance and can be represented by an integer (higher integer means better performance), and no two people have the same performance. The performance of the initial employees are represented by an array of integers $ A = [A_1, A_2, \dots, A_N] $ where $ A_i $ is the performance of the $ i^{th} $ employee. Randall is employee $ 1 $ , so his performance is $ A_1 $ . We will consider the first $ M $ years. At the end of the $ i^{th} $ year, the company replaces its $ R_i $ worst-performing employees and replaces with $ R_i $ new employees. The performance of these new employees are represented by an array of integers $ B_i = [(B_i)_1, (B_i)_2, \dots, (B_i)_{R_i}] $ where $ (B_i)_j $ is the performance of the $ j^{th} $ new employee. He will consider $ Q $ scenarios. On the $ i^{th} $ scenario, he will change the value of $ (B_{X_i})_{Y_i} $ to $ Z_i $ . For each scenario, Randall is wondering whether he will still be in the company after $ M $ years. Note that the changes in each scenario are kept for the subsequent scenarios.

输入输出格式

输入格式

Input begins with a line containing three integers: $ N $ $ M $ $ Q $ ( $ 2 \le N \le 100\,000 $ ; $ 1 \le M, Q \le 100\,000 $ ) representing the number of employees, the number of years to be considered, and the number of scenarios, respectively. The next line contains $ N $ integers: $ A_i $ ( $ 0 \le A_i \le 10^9 $ ) representing the performance of the initial employees. The next $ M $ lines each contains several integers: $ R_i $ $ (B_i)_1 $ , $ (B_i)_2 $ , $ \cdots $ , $ (B_i)_{R_i} $ ( $ 1 \le R_i < N $ ; $ 0 \le (B_i)_j \le 10^9 $ ) representing the number of employees replaced and the performance of the new employees, respectively. It is guaranteed that the sum of $ R_i $ does not exceed $ 10^6 $ . The next $ Q $ lines each contains three integers: $ X_i $ $ Y_i $ $ Z_i $ ( $ 1 \le X_i \le M $ ; $ 1 \le Y_i \le R_{(X_i)} $ ; $ 0 \le Z_i \le 10^9 $ ) representing a scenario. It is guaranteed that all integers in all $ A_i $ , $ (B_i)_j $ , and $ Z_i $ (combined together) are distinct.

输出格式

For each scenario in the same order as input, output in a line an integer $ 0 $ if Randall will not be in the company after $ M $ years, or $ 1 $ if Randall will still be in the company after $ M $ years.

输入输出样例

输入样例 #1

5 3 3
50 40 30 20 10
4 1 2 3 100
1 4
2 6 7
1 3 300
2 1 400
2 1 5

输出样例 #1

1
0
1

说明

Explanation for the sample input/output #1 Randall performance is represented by $ 50 $ . For the first scenario, the value of $ (B_1)_3 $ is updated to $ 300 $ , causes the following: - Initially, the performance of the employees is $ [50, 40, 30, 20, 10] $ . - At the end of the first year, $ 4 $ worst-performing employees are replaced by employees with performance $ [300, 100, 2, 1] $ . Therefore, the performance of the employees is $ [300, 100, 50, 2, 1] $ . - At the end of the second year, the performance of the employees is $ [300, 100, 50, 4, 2] $ . - At the end of the third year, the performance of the employees is $ [300, 100, 50, 7, 6] $ . Therefore, Randall will still be in the company after $ 3 $ years.For the second scenario, the value of $ (B_2)_1 $ is updated to $ 400 $ , causes the following: - Initially, the performance of the employees is $ [50, 40, 30, 20, 10] $ . - At the end of the first year, the performance of the employees is $ [300, 100, 50, 2, 1] $ . Recall that the change in the first scenario is kept for this scenario as well. - At the end of the second year, the performance of the employees is $ [400, 300, 100, 50, 2] $ . - At the end of the third year, the performance of the employees is $ [400, 300, 100, 7, 6] $ . Therefore, Randall will not be in the company after $ 3 $ years.