## T1 bargain
> Operation 1 denotes "Choose a digit and delete it", and operation 2 denotes deleteing all the remaining digits in one go.
> Hint 1: When operation 2 is better than operation 1?
> Hint 2: Enumerate from right to left.
It's easy to notice that we won't leave too much digits for operation 2. Furthermore, the number of left digits, $k$, won't exceed 5, since $10^k > k\cdot 10^5$ for all $k>5$.
Consider dynamic programming. Let $f_{i,j}$ be the minimum cost to delete all the **last** $i$ digits, while $j$ digits are deleted using operation 2.
Let $c_i$ be the $i$-th digit of $n$, counting from the least significant digit. Now we have the following transition:
- $f_{i,j} \gets f_{i-1,j} + v_{c_i}$ (operation 1)
- $f_{i,j} \gets f_{i-1,j-1} + c_i \cdot 10^{j-1}$ (operation 2)
Thus, we can solve this problem in $O(k\log n)$ time, where $k=5$ in this case.
## T2 water
> The hardest problem in this round!
>
> Operation 1 denotes subtraction, and operation 2 denotes addition.
> Hint 1: Adjust the order of the operations.
> Hint 2: Can you determine whether a sequence of operation 1 is valid?
> Hint 3: Use binary search.
We need some observations to make this problem easier.
> **Observation 1**
>
> One can always use all operation 1 before any operation 2.
It's straightforward, so I omit the proof.
However, it leads to the first key observation:
> **Observation 2**
>
> Let $a'_i$ be the temperature of vertex $i$ after we use up operation 1.
>
> The answer is yes (i.e. `Huoyu`) if and only if $\forall j \in \text{son}_i, a'_j \le a'_i$, and $a'_1 \le 0$.
To proof it, consider the root. Since we can only increase the temperature using operation 2, $a'_{root} \le 0$ should hold. Then we add $-a_{root}$ to the root, and for every son $j$, there should be $a'_j \le a'_{root}$, or $a'_j$ will remain positive.
Now the temperature of root is $0$, so we can simply remove it and check the remain forest. The above observation can then be proved by induction. $\square$
Let $x_i$ be the number of operation 1 done on vertex $i$. (If $i$ isn't a leaf, we can simply let $x_i = \sum\limits_{j\in \text{son}_i} x_j$.)
We need to check whether we can managed to satisfy the following inequalities:
$$
\forall j \in \text{son}_j, a_i - x_i \ge a_j - x_j \\
x_1 \ge a_1
$$
However, it seems impossible to maintain the information, since $a_i$ and $x_i$ can be extremely large. So we need observation 3:
> **Observation 3**
>
> for all vertex $i$, there exists an interval $[l_i, r_i]$ (possibly empty), such that $x_i = p$ is valid (with all the constraints inside subtree $i$) $\iff p \in [l_i,r_i]$.
The proof also needs induction.
Firstly, $l_i$ is easy to compute: $l_i = \max\{\sum\limits_{j \in \text{son}_i}l_j, a_i\}$. Suppose we know $r_i$, and every subtree satisfy the above lemma.
It's obvious that we only need to consider the case where there aren't any empty intervals.
Suppose $x_i=p\ (p>l_i)$ is valid. Now we need to proof $x_i=p-1$ is also valid.
There must exist a $j \in \text{son}_i$ whose $x_j > l_i$, or $p > l_i$ is violated. Then we decrease $x_j$ by $1$.
For $j$, $a_i - x_i \ge a_j - x_j$ still holds, since we decrease $1$ at both sides of the inequality; and for $k$ other than $j$, the left hand side increases by $1$ while the right hand side remains the same.
Thus, $x_i=p-1$ is still valid. $\square$
One corner case is that $|\text{son}_i|=1$, then we simply need to inherit $[l,r]$ from its son.
Given observation 3, a fan of Um_nik should immediately come up with **binary search**.
In detail, we can first compute $l_i$, then use binary search to compute $r_i$. We only need to check whether $x_i = p$ is valid.
Enumerate $j$ through every son vertex of $i$. Since $a_i - x_i \ge a_j - x_j$ we have $x_j \le a_i-a_j+x_j$. So $x_j \in [l_i, \min\{r_i,a_i-a_j+x_j\}]$. If this interval is empty then $p$ is obviously invalid.
Otherwise, we can compute bound of $x_i$ by summing up all these intervals, and $p$ is valid iff it falls into such bound.
Thus, we can solve the problem in $O(n \log V)$ time.
Please take care of the bound while binary searching, and maybe `__int128` is neccessary in some cases.
## T3 anti
> Hint 1: solve the 2/5 scored problem, i.e. come up with a solution without maximizing k.
> Hint 2: solve Special Property B, i.e. $\Sigma=2$.
> This is a **deterministic** approach, which needs some case work.
Consider when the answer is no (i.e. `Shuiniao`).
- If $s$ only contains one kind of character; Or
- If $s$ only contains two kinds of character, and the second kind only occurs at the middle of string (i.e n is odd and only $s_{(n+1)/2}$ is different from the rest).
It's obvious that such condition is sufficient.
We can also show that such condition are necessary, by giving a construction of the answer sequence.
After we exclude the situation with no solution, one should consider how to maximize $k$. After examining `anti2.ans` one should notice **almost every** subsequence has length $2$. It is because 2 different characters can form a valid subsequence, which seems optimal.
### stage 0
So, if we only need to calculate k, one can easily come up with a greedy solution: Every time, we pick 2 diffrent characters with the maximum and the second maximum times of occurrence. Then we pack the first occurrence of both characters into a subsequence, and remove such 2 occurrence.
It's not hard to proof that k is maximized. If $s$ becomes empty then we can directly output the answer. Otherwise we need to merge the remaining letters into existed subsequences.
Obviously, only 1 kind of character will remain in $s$. WLOG let `a` be such character.
### stage 1
We enumerate from $1$ to $n$. If $s_i \neq \mathtt a$ we merge every remaining `a` before $i$ into the subsequence which $i$ belongs to.
It can be shown that, after this stage, only a trailing sequence of `a`(possibly empty) will remain. Every `a` before any character other than `a` will be removed.
### stage 2
Let $l_i$ be the number of `a`s in the subsequence which $i$ belongs to, on the left of $i$. Specially, if $i$ is **not** matched with an `a` in **stage 0**, let $l_i=0$.
Let $d$ be the length of the remaining `a` sequence.
If there exists an $i$ where $s_i \neq \mathtt{a} \land l_i \neq d$ we can simply append all the remaining `a` after $i$.
Otherwise, if there exists more than $1$ $i$ satisfying $s_i \neq \mathtt a$:
Let $p,q$ be the first two such $i$.
- If $d>1$ we can append the first remaining `a` after $p$, and the rest after $q$.
- Otherwise we can move the first `a` with $p$ to the belonging subsequence of $q$. Now $q$ will have two `a`s before it, and nothing behind it, and $p$ will be alone. Then, we can directly append the remaining `a`(only $1$) after $p$.
Otherwise, there will be no solution, as the string must satisfy one of the condition given above.
Thus, we solved this problem in $O(n \log n)$ time. Note that we need to sort the subsequence. Maybe careful implementation can reach linear complexity.
## T4 show
> Hint 1: solve Special Property D.
> Hint 2: consider sqrt balancing.
It is not hard for one to notice, given $r$, troupe in room $p$ exits if and only if $l \le q_p$, where $q_p$ is a constant which only depends on $r$ and $p$. (Specially, let $q_1=r$.)
Consider maintaining $q_p$ as we move $r$ from $1$ to $k$.
Suppose we move to $i$ from $i-1$. Only $q_{a_i}$ is affected, which becomes $\max\limits_{v \in \text{out}_{a_i}}\{q_v\}$.
So the problem is translated into a form of 2D counting, because we only need to count $\sum_{i} [q_i \ge l]$, which can be done in $O((n+q) \log n)$ time by storing all the queries in advance and using fenwick tree.
However maintaining $q_p$ is of wrong complexity, since the out degree of a vertex can be large.
Use the balancing trick. For all vertices $x$ with out degree greater than $B$, we can maintain $q_x$ when updating $q_{a_i}$; for other vertices, we can simply enumerate through the edges. Choose $B=\sqrt n$, and we can complete this in $O(n \sqrt n)$ time.