C2331 - Go to School By Bus

A key observation is that by taking the bus at stop $i$, the time arrived at stop $i+1$ will be the same no matter what time Dragon arrives at stop $i$.
Let $v[i]$ be $\sum_{k=0}^{i}W[k]-T[k]$.
It can be observed that Dragon can only get from stop $j$ to stop $i$ in time when: $v[j]\le v[i]$.
Let $dp[i]$ where $i$ is the number of taken routes be the maximum $v[j]$ among all stops $j$ that can be reached with exactly $i$ routes.
For stop $i$, the minimum number of routes required to take the bus at stop $i$ is the minimum $j$ such that: $$dp[j]\le v[i]$$ After so, we update $dp[j+1]$ to be $v[i+1]$.
To speed up this DP, we can use a binary search on range maximum query point update segment tree on $dp$.
As every query spans the entire $dp$ array, on the segment $[l,r]$, it is optimal to choose segment $[l, mid]$ if the maximum $dp$ in the segment $\le v[i]$, else choose segment $[mid+1, r]$.
Note that before stop $1$, update $dp[0] = v[0]$.

C2332 - Rock's Great Escape

A naive DP solution:
Let $dp[i]$ be the minimum number of chocolate coins to get to cell $i$.
$$dp[i] = min_{i-k\le j\le i}(dp[j]+c[i])$$ This solution is $O(N^3)$ by iterating through all values of $K$.
We can improve this by performing binary search on $K$ to achieve $O(N^2logN)$.
To speed up the DP calculation, we can use monotone queue optimisation to achieve $O(NlogN)$.

C2333 - Paper Palindrome

Consider an overlapping of $a[i]$ and $a[j]$. If $a[i]=a[j]$, its obvious that no change is needed as further changes can be done after this flip with less cost.
When $a[i]$ and $a[j]$ are different, we only change either $a[i]$ to $a[j]$ or vice versa with the same logic above.
As we cannot determine whether it is better to change to $a[i]$ or $a[j]$ in this overlapping, we save both values in a BST (e.g. map, set) in $BST[i]$ for later overlappings.
When considering overlap $a[i]$ and $a[j]$, we merge all saved values in $BST[i]$ and $BST[j]$.
If the greatest frequency is 1, we increment the final cost.
If there exists only one most frequent value, we should choose that value to change to among all overlaps saved.
Otherwise, we only save all most frequent values in $BST[i]$ and setting their frequencies to 1.
Example: $A=[1,2,1,2,2,2]$ using map (value->freq):
$\{[1, 1]\}, \{[2, 1]\}, \{[1, 1]\}, \{[2,1]\}, \{[2, 1]\}, \{[2, 1]\}$ $ans=0$
fold
$\{[1, 1], [2,1]\}, \{[2, 1]\}, \{[1,1],[2, 1]\}$ $ans=2$
fold
$\{[1,1],[2,1]\},\{[2,1]\}$ $ans=2$
fold
$\{[2,1]\}$ $ans=2$

C2334 - Clay Battalion

We can actually turn this problem into a segment tree problem by using DFS order of the hierarchy tree.
Reindex the tree in its pre-order traversal. For instance, using sample 1, the new indices of $[1, 2, 3, 4, 5]$ could possibly be $[1, 2, 5, 3, 4]$.
Querying subtree rooted at $2$, for instance, now refers to querying the segment $[2, 3, 4]$ in the new indices. (Trivial right if know HLD)
Now the problem decomposes into a range update, range query problem, because the indices for a subtree is now contiguous.
But how to handle the lazy propagation in $max$ and addition updates?
Define $lazy[i] = [a, b]$ for each node in the segment tree where it updates the node $st[i]$ to $max(st[i], a)+b$.

1. To merge an addition update, $lazy[i]=[a,b+v]$.
2. To merge a $max$ update, $lazy[i] = [max(a, v-b),b]$.
   $max(max(st[i], a) + b, v) = max(max(st[i], a), v-b)+b = max(st[i], max(a, v-b))+b$
   

Note function composition is always associative: $f \cdot g \cdot h = (f \cdot g) \cdot h = f \cdot (g \cdot h)$, where $f \cdot g$ means $g(f(x))$
fancy way of saying lazy propagation is correct because evaluation order doesn't matter (but obviously $f\cdot g \neq g \cdot f$, don't mess up)