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

lzyqwq · 2025-11-21 15:58:25 · 题解

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

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

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