P10673 [MX-S1-T2] Catalyst

Original problem link: 。

Children really like candies。 Now, Little K has some candies, and each candy has a number on it representing its type。 There are $q$ events. Each event either adds a candy, removes a candy, or asks a query。 Each query gives an integer $k$, meaning that Little K now needs to distribute all candies to $k$ children, and each child must receive at least one candy. At the same time, children do not like receiving identical candies. Specifically, when a child receives candy type $i$, if they have already received candy type $i$ before that, then they will get very angry, and their anger value increases by $1$。 Little K does not like seeing children angry, but Little K cannot solve such a difficult problem, so you need to help Little K find a way to distribute the candies that minimizes the sum of all children’s anger values。 It is guaranteed that there exists a distribution plan such that every child gets at least one candy。 Each query does not actually perform the distribution, i.e. after each query, the candies owned by Little K do not change。 Note that the candy distribution process can be understood as partitioning all candies owned by Little K into $k$ non-empty sequences, and you may reorder the candies。

The first line contains two positive integers $n,q$。 The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$, describing the candies Little K initially has。 The next $q$ lines each contain two positive integers describing an operation. There are three possible inputs: `1 x`: Little K gains one more candy of type $x$。 `2 x`: Little K loses one candy of type $x$. It is guaranteed that at this time Little K has at least one candy of type $x$。 `3 k`: Little K needs to distribute the candies to $k$ children. You need to output the minimum possible sum of all children’s anger values. Let $S$ be the number of candies Little K currently has, and it is guaranteed that $1\le k\le S$。

For each query, output one line with one integer, the answer you computed。

__Sample Explanation 1__ In the first query, the candies in Little K’s hand are $\{3,5,2,5,5\}$. Distribute them to $2$ children as $\{2,3,5\},\{5,5\}$. The children’s anger values are $0,1$. It can be proven that there is no plan with a smaller sum of anger values。 __Constraints__ __This problem uses bundled subtasks for judging。__ For $100\%$ of the data, $1\le n,q\le 10^6$, $1\le a_i,x\le n$. In each query, let $S$ be the number of candies Little K currently has, and it is guaranteed that $1\le k\le S$。 | Subtask ID | $n\le $ | $q\le $ | Special Property | Score | | ---------- | ------- | ------- | ---------------- | ----- | | $1$ | $5$ | $15$ | None | $20$ | | $2$ | $2000$ | $2000$ | None | $20$ | | $3$ | $10^5$ | $10^5$ | None | $20$ | | $4$ | $10^6$ | $10^6$ | $a_i,x\le 50$ | $10$ | | $5$ | $10^6$ | $10^6$ | $k\le 50$ | $10$ | | $6$ | $10^6$ | $10^6$ | None | $20$ | Translated by ChatGPT 5