P11364题解

· · 题解

本题解仅作为其他题解的补充

许多题解形如转化为查询

\underset{l \le i \le r-k}{max} \{ \underset{i \le j \le i+k}{min\;t_j} \}

设pre_i为最小的下标，使得\underset{pre_i \le j \le i}{min} = t_i， 设nxt_i为最大的下标，使得\underset{i \le j \le nxt_i}{min} = t_i，nxt_i和pre_i不难用单调栈快速求出

那么t_i能对询问j产生贡献，当且仅当

min \{ r_j,nxt_i \} - max \{ l_j,pre_i \}+1 \ge k_j \land l \le i \le r

即

nxt_i-pre_i+1\ge k_j\land nxt_i-l_j+1\ge k_j\land r_j-pre_i+1\ge k_j\land l \le i \le r

移项得

nxt_i-pre_i+1\ge k_j\land nxt_i\ge k_j+l_j-1\land pre_i\le r_j-k_j+1\land l \le i \le r

很多题解并没有加上l \le i \le r这一条件，尽管去掉它并不对答案产生影响，但先前的题解似乎并没有证明这一点的

下面给出其证明

假设有一个满足nxt_i-pre_i+1\ge k_j\land nxt_i\ge k_j+l_j-1\land pre_i\le r_j-k_j+1\land i<l 下标最大的i会对j产生贡献，则对于满足i<w \le nxt_i且t_w最小的w而言pre_w \le i+1,nxt_w = nxt_i

其中t_w = t_i时pre_w = pre_i否则pre_w = i+1

对于nxt_w-pre_w+1\ge k_j

因为i<l所以pre_w\le l，加之nxt_w\ge k_j+l_j-1移项可得条件成立

对于nxt_w\ge k_j+l_j-1

显然成立

对于pre_w\le r_j-k_j+1

于是可得$t_w$也会对$j$产生贡献，同时 $t_w \ge t_i$，所以$w$的贡献会覆盖掉$i$的贡献，$w>i$而$i$为满足上述偏序条件最大的下标，所以$w\ge l

若w\le r 则本题做完了，l \le i \le r可以去掉

否则，我们再找到满足i<v<w的t_v最小的v，同理，他也一定满足上述偏序关系，会产生贡献，如此不断缩小区间，一定能找到一个满足上述偏序关系的下标u且l \le u \le r，t_u能造成贡献，覆盖掉前面一切不合法的贡献

所以去掉$ l \le i \le r$并不会对答案造成影响，证毕