T1 Selection of color pens (rgb)
Signed the question, but didn't sign it.
I didn't realize the 3-D prefix and, straight up, a bitset.
It is straightforward to dichotomize the answer, and then enumerate the starting points of the intervals in each dimension of the three dimensions, the prefixes and the number of lookups to see if the number of prefixes and lookups is greater than or equal to $ K $ that is, or you can change the dichotomized answer to be a two-pointer in the first dimension, with less than one $ log $ .
T2 Soldier Ant Sort
It's more signed than T1, but it doesn't say freopen hangs 100.
Go from $ b $ array to $ a $ array and $ O(n) $ pull it over.
T3 Population Bureau DBA (dba)
Math pushes the equation.
But there are a lot of partially-scored digit DPs that cheat 97 points.
It is simply the number of solutions to an equation satisfying $ x_1 + x_2 + x_3 + ------ + x_{n-1} + x_{n} = sum , x1 \lt p , \forall \ \ \ i ∈ [1,n] \ \ 0 \le x_i \lt m $ .
First disregard the restriction of $ x1 \lt p $, then you can tolerate the repulsion, chinning that there are $ k $ x $ that are greater than $ m $, repel them, and have an equation (direct plugboard):
If you consider the restriction on $ x1 \lt p $ , then it is straightforward to enumerate $ x1 $ , so there:
The simplification of the summation after that is because the one underneath the combinatorial number doesn't change, so it's a vertical column in Yang Hui's trigonometry.
As pictured:
T4 Origin of banks (banking)
I'll keep this one simple because I've talked about it before. Never mind, let's go into a little more detail.
First consider how to find when there is only one bank, then surely everyone runs to one bank, so enumerate the points and then count the contributions?
There are actually $ O (n) $ ways to do this kind of problem.
Starting with 1 as the root, we directly consider the contribution of each edge, for an edge whose weight is $ w $ , connecting the point $ j $ to his father $ fa_j $ .
For this edge, either $ j $ and the points in his subtree go up through this edge, or the points above come down, then we set $ sz_j $ is the sum of the weights of $ j $ and the points in his subtree, and $ tot $ denotes the sum of the weights of the whole tree, and we can directly take $ w \times \min( sz_j , tot - sz_j) $ as the contribution of this edge.
Why yes, to prove it:
The above equation only guarantees that it is optimal for one edge, but not globally, but in fact global optimality can be shown to hold only when each is optimal.
Proof of completion. At this point we have $ O(n) $ the solution to the problem for one bank. What if there are two banks, at this point there must also be an edge with no one walking on it, so we enumerate an edge and disconnect it, then sum the contributions for each of the two trees to $ O(n^2) $ solve it.
$ O(n^2) $ Can't be solved, so let's see if we can get on to data structure optimization.
Optimization must start from the contribution side, then look at that contribution equation, $ ans_j = w_j \times \min( sz_j , tot - sz_j ) $ , this min is very difficult to optimize directly, then sub-discussion, if $ sz_j \le \frac{tot}{2} , ans_j = w_j \times sz_j $ , otherwise $ ans_j = w_j \times (tot - sz_j ) $ , then this thing can be on the value field line segment tree, specifically, for $ sz $ open a value field line segment tree, and then maintain $ \sum w_j, \sum w_j \times sz_j $ and then you can do.
The main idea is there, analyze it specifically:
Inside this figure, we split the tree into two parts, a red one and a green one, and we seek contributions from each.
For the green part it's good, just use what we just did as far as the line tree is concerned, the line tree is merged $ n( log (n) ) $ at dfs, for the red part it's a little tricky.
First consider how the red part has changed relative to the original tree:
Red Tree's $ tot = sz_1 - sz_j $
For the root $ j $ in the green tree, $ sz_i $ is reduced by $ sz_j $ for all points $ i $ above this chain from his father $ x $ to 1.
First of all, the contribution of the points on the chain must be a single request, you can maintain a tree array, and then each query first chain subtraction, and then ask, but a trick can be used without the chain subtraction, now the conditions of the sub-discussion is $ sz_i - sz_j \le \frac{tot}{2} $, then directly move the item, the conditions of the sub-discussion to $ sz_i \le \frac{tot}{2} + sz_j $ and the final answer will be the value after subtracting $ sz_j $ . (Write out the equation and you'll be able to)
Next is the part of the mangrove tree in addition to the chain, we found that this part is difficult to directly seek, the line tree is not well maintained, but he is the global in addition to the chain and the green tree in addition to all the points, so we find out the global contribution to $ \frac{tot}{2} $, this part can be a static global line tree, you can also directly discretize the prefix after the sum and , and then subtracted from the chain as well as the green tree and then subtract the contributions to $ \frac{tot}{2} $ from the chain and the green tree. This part can be solved directly with what we just maintained.
Then we're done begging, and this question is mostly just a matter of paying more attention to attention to detail.