题解：P17131 [ICPC 2025 Shanghai R] No more regrets

Eterna · 2026-07-21 19:49:36 · 题解

这个题可以单侧递归线段树。

我们在线段树结点上至少要维护前缀最大值之和、前缀最小值之和、答案。

前两者简单，考虑维护答案怎么办，记结点 u 的答案为 \mathrm{ans}_u。

写成 \mathrm{ans}_u=\mathrm{ans}_{\mathrm{ls}(u)}+\mathrm{sol}(\mathrm{rs},\max_{\mathrm{ls}},\min_{\mathrm{ls}})。

其中 \mathrm{sol}(u,x,y)=\sum_{i=l}^{r}\max\{\max_{j=l}^{i}a_j,x\}\times \min\{\min_{j=l}^{i}a_j,y\}。其中 [l,r] 是 u 对应的线段树结点。

要计算 \mathrm{sol}(u,x,y)，可以讨论情况：

2. 如果直接这样递归计算，单次复杂度为 $\mathcal{O}(\log^2 n)$，考虑继续优化。容易发现 $\mathrm{sol}(\mathrm{rs},\max_{\mathrm{ls}},y)=\sum_{i=\mathrm{mid}+1}^{r}(\max_{j=l}^{i}a_j)\times \min\{\min_{j=l}^{i}a_j,y\}=\mathrm{sol}(u,-\infty,y)-\mathrm{sol}(\mathrm{ls},-\infty,y)$。相当于删除了一边限制，同样是简单的单侧递归。均可以 $\mathcal{O}(\log n)$ 解决。

容易发现情况 2. 或情况 3. 均可以直接在 \mathcal{O}(\log n) 的复杂度内求解，其余情况只会向单侧递归，故我们可以在 \mathcal{O}(\log n) 的时间复杂度内求出 \mathrm{sol}(u,x,y)。

修改是简单的，维护一些标记即可。

于是整个问题容易在 \mathcal{O}\big(q \log^2 n+n \log n\big) 的时间复杂度内解决。空间复杂度为 \mathcal{O}(n)。