单调栈

CF671E Organizing a Race

记 \(a_i = \sum_{j = 1}^{i - 1} g_j - \sum_{j = 1}^{i - 1} w_j,\, b_i = \sum_{j = i + 1}^n g_j - \sum_{j = i}^{n - 1} w_j\)，则区间 \([l, r]\) 合法的充要条件为 \(\forall i \in [l, r], a_i \ge a_l \land b_i \ge b_r\)。

当 \(g_i \leftarrow g_i + 1\) 时，\(\forall j \in [i + 1, n], a_j \leftarrow a_j + 1,\, \forall j \in [1, i - 1], b_j \leftarrow b_j + 1\)。

我们固定区间 \([l, r]\)，试判断这个区间是否能在 \(k\) 次操作内变得合法。

首先我们需要满足 \(a_i\) 的限制。不难发现我们只需要关注 \([l, r]\) 内 \(a_i\) 的严格前缀最小值，记它们的下标为 \(p_1 < p_2 < \dots < p_k\)。我们会让每个操作位置尽可能靠右，这样更有利于满足 \(b_i\) 的限制。因此我们的操作可以表示为 \(\forall i \in [2, k], g_{p_i - 1} \leftarrow g_{p_i - 1} + a_{p_{i - 1}} - a_{p_i}\)。

记经过上述操作后 \(b_i\) 变为 \(b^{\prime}_i\)。剩余的 \(k - a_l + a_{p_k}\) 次操作一定在 \(r\) 处使用最优，即我们合法的充要条件为 \(\forall i \in [l, r], b^{\prime}_i \ge b_r - k + a_l - a_{p_k}\)。

考虑从 \(n\) 到 \(1\) 枚举 \(l\)，用单调栈维护 \([l, n]\) 内 \(a_i\) 的严格前缀最小值下标 \(q_1 < q_2 < \dots < q_m\)。同时，用线段树维护出经过区间 \([l, n]\) 的上述操作后 \(b_i\) 的值 \(t_i\)。

不妨先二分找到最小的 \(q_{x}\) 满足 \(a_l - a_{q_x} > k\)。当且仅当 \(r \le q_x - 1\) 时，区间 \([l, r]\) 能在 \(\le k\) 次操作中满足 \(a_i\) 的限制。

考察区间 \([l, r]\)，我们此时维护的 \(t_i\) 是经过区间 \([l, n]\) 的操作后，而非经过区间 \([l, r]\) 的操作后的 \(b_i\)。由于我们只关心 \(b_i\) 的相对大小，不妨把 \(g_i \leftarrow g_i + 1\) 对 \(b_i\) 的影响改为 \(\forall j \in [i, n], b_j \leftarrow b_j - 1\)。这样，我们维护的 \(t_i\) 在 \(i \in [l, r - 1]\) 时就确实是经过区间 \([l, r]\) 的操作后的 \(b_i\)。区间 \([l, r]\) 合法的充要条件也改为 \(r < q_{x} \land \forall i \in [l, r - 1], t_i \ge b_r - k\)。

不难发现我们可以判断是否有 \(r \in [s, t]\) 使得区间 \([l, r]\) 合法。具体地，只需要判断 \(\min_{i \in [l, s - 1]} t_i \ge \min_{i \in [s, t]} b_i - k\)。这是因为 \(t_i \ge b_i - k\)，因此 \([s, t]\) 中的最小值 \(b_p\) 一定满足 \(\min_{i \in [s, p - 1]} t_i \ge b_p - k\)，因此只需要判断上述式子是否成立。

找出 \(q_x\) 后，可以在线段树上提取出区间 \([l, q_x - 1]\)，然后线段树上二分即可找到最长的合法 \([l, r]\)。

时间复杂度 \(O(n \log n)\)。

提交记录