Deltix Round, Autumn 2021 (Div. 1 + Div. 2)
Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
E. William The Oblivious
solution 1: (dynamic divide and conquer / segment tree)
\[ \begin{aligned} Ans =& \min_{l\le r}\{S[0,l)\#a+S[l,r)\#b+S[r,n)\#c\} \\ =& \ S\#b+\min_{l\le r}\{S[0,l)\#(a-b)+S[r,n)\#(c-b)\} \end{aligned} \]
线段树维护区间最小前缀、后缀、答案即可。
solution 2: (DDP)
WIP
F. Interesting Sections
\[ Ans=\sum_{l\le r}[\mathrm{popcnt}(\min\{a_l\dots a_r\}) = \mathrm{popcnt}(\max\\a_l\dots a_r\})] \]
应用单调栈+线段树维护最大值个数。
time: \(O(n\log \max a+n\log n)\)
space: \(O(n)\)
G. A Stroll Around the Matrix
思路：先考虑静态问题，构造最优解/通过作差（微调法）将高维问题降维处理。