题解：P13963 [ICPC 2023 Nanjing R] 接雨水

ran_qwq · 2025-09-05 08:32:51 · 题解

典中典巨大 ds。

考虑一次 a_x\leftarrow y 的修改对 f,g 的贡献。它会使得 \forall i\in[x,n],f_i\leftarrow\max(f_i,y)，以及 \forall i\in[1,x],g_i\leftarrow\max(g_i,y)。

因为 f 单调不降，g 单调不升，所以变化的都是一段区间，考虑二分出这段区间转化为区间推平。维护区间最小值，以 f 的修改区间为例，在线段树上二分，如果右区间最小值 \ge y 就往左走，否则往右走，g 是同理的。

接下来看怎么求 \sum\min(f_i,g_i)。根据 f 单调不降，g 单调不升，\min(f_i,g_i) 取到 f 是一个前缀，取到 g 是一个后缀，二分出临界点即可。

代码中 mf、mg、lf、lg、tf、tg、sf 和 sg 分别表示 f 最小值、g 最小值、左端点 f 值、左端点 g 值、f 推平懒标记、g 推平懒标记、f 和以及 g 和。

这是代码。