P15681 Candy Distribution.

You are given a sequence $a_1,a_2,\dots,a_n$ of length $n$ and $q$ operations. There are two types of operations in total: 1. Given $x,y$, you need to modify the value of $a_x$ to $y$. 2. Given $m,k$, you need to compute the following: suppose there are currently $m$ baskets and $n$ people. The $i$-th person will choose $a_i$ **distinct** baskets and put $1$ candy into each of these $a_i$ baskets. Find the maximum possible number of baskets that end up with **exactly** $k$ candies.

The first line contains three integers $c,n,q$, where $c$ denotes the test point ID. The samples satisfy $c=0$. The second line contains $n$ integers $a_1,a_2,\dots,a_n$. The next $q$ lines each contain three integers, in the form $1\ x\ y$ or $2\ m\ k$, representing the first type of operation and the second type of operation, respectively.

For each operation of the second type, output one line containing one integer, which is the answer.

### Explanation for Sample 1 - For the first operation, $a=\{1,2,5\}$, $m=5$, $k=2$. Person $1$ can choose to put $1$ candy into basket $1$. Person $2$ can choose to put $1$ candy into basket $2$ and basket $3$. Person $3$ can only choose to put $1$ candy into all baskets. Then baskets $1,2,3$ each have exactly $2$ candies. It is easy to prove that this maximizes the number of baskets with exactly $2$ candies. - For the third operation, $a=\{1,2,3\}$, $m=4$, $k=1$. Person $1$ can choose to put $1$ candy into basket $1$. Person $2$ can choose to put $1$ candy into basket $1$ and basket $2$. Person $3$ can choose to put $1$ candy into baskets $1,3,4$. Then baskets $2,3,4$ each have exactly $1$ candy. It is easy to prove that this maximizes the number of baskets with exactly $1$ candy. - For the fourth operation, $a=\{1,2,3\}$, $m=5$, $k=0$. Person $1$ can choose to put $1$ candy into basket $1$. Person $2$ can choose to put $1$ candy into basket $1$ and basket $2$. Person $3$ can choose to put $1$ candy into baskets $1,2,3$. Then basket $4$ and basket $5$ each have exactly $1$ candy. It is easy to prove that this maximizes the number of baskets with exactly $0$ candies. ### Sample 2 See `candy/candy2.in` and `candy/candy2.ans`. This sample set satisfies the constraints of test point $4$. ### Sample 3 See `candy/candy3.in` and `candy/candy3.ans`. This sample set satisfies the constraints of test point $9$. ### Sample 4 See `candy/candy4.in` and `candy/candy4.ans`. This sample set satisfies the constraints of test point $10$. ### Sample 5 See `candy/candy5.in` and `candy/candy5.ans`. This sample set satisfies the constraints of test point $15$. ### Sample 6 See `candy/candy6.in` and `candy/candy6.ans`. This sample set satisfies the constraints of test point $17$. ### Sample 7 See `candy/candy7.in` and `candy/candy7.ans`. This sample set satisfies the constraints of test point $18$. ### Sample 8 See `candy/candy8.in` and `candy/candy8.ans`. This sample set satisfies the constraints of test point $20$. ### Constraints For all testdata, it is guaranteed that: - $1 \le n,q \le 5\times10^5$. - $1 \le a_i \le 10^6$. - $1 \le x \le n$, $1 \le y \le 10^6$. - $\max a_i \le m \le 10^{12}$, $0 \le k \le n$. ::cute-table{tuack} | Test point ID | $n,q\le$ | Special property | | :-----------: | :-----------: | :--------------: | | $1$ | $5$ | A | | $2$ | $5$ | B | | $3$ | $400$ | BC | | $4\sim5$ | $400$ | None | | $6$ | $5000$ | BC | | $7$ | $5000$ | B | | $8$ | $5000$ | C | | $9$ | $5000$ | None | | $10$ | $10^5$ | BC | | $11$ | $10^5$ | B | | $12$ | $10^5$ | C | | $13\sim14$ | $10^5$ | None | | $15$ | $5\times10^5$ | A | | $16$ | $5\times10^5$ | BC | | $17$ | $5\times10^5$ | B | | $18$ | $5\times10^5$ | C | | $19\sim20$ | $5\times10^5$ | None | - Special property A: it is guaranteed that $m \le 7$. - Special property B: it is guaranteed that $m=10^{12}$. - Special property C: it is guaranteed that there is no operation of the first type. Translated by ChatGPT 5