题解：P14468 [COCI 2025/2026 #1] 和谐 / Harmonija

一开始没看到对于每个 $i=1,2,3,\dots,k$ 都要满足条件认为这是不可做题。

先考虑序列问题，容易列出状态转移方程，将其写成矩阵形式就是所有矩阵做 $(+,\max)$ 矩阵乘法。

那么一次询问相当于在树链查询矩阵积。重链剖分，直接硬上线段树维护区间矩阵积是 2log，但是注意到除了最顶上的重链之外，其余重链的贡献都是以链顶开始的一段前缀的矩阵积，所以可以再预处理前缀矩阵积，这样跳链的过程可以 $\mathcal{O}(1)$ 查询，最后一条链要 $\mathcal{O}(\log n)$ 查询，就做到 1log 了。