2020-2021:teams:alchemist:mountvoom:halltheorem
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:mountvoom:halltheorem [2020/05/12 10:26] mountvoom |
2020-2021:teams:alchemist:mountvoom:halltheorem [2020/05/12 10:29] (当前版本) mountvoom |
||
|---|---|---|---|
| 行 33: | 行 33: | ||
| $\forall 1\le i< j\le n, pre[l_i-1]-p[i-1]\le pre[r_j]-p[j]$ | $\forall 1\le i< j\le n, pre[l_i-1]-p[i-1]\le pre[r_j]-p[j]$ | ||
| - | 于是可以对每个位置维护一个$pre[l_{i + 1} - 1] - p[i - 1]$和$pre[r_j] - p[j]$ | + | 于是可以对每个位置维护一个$pre[l_{i + 1} - 1] - p[i]$和$pre[r_i] - p[i]$，注意此时$i \in [0, n]$ |
| + | |||
| + | 其中$pre[i]$是是定值，$p[i]$可以用线段树轻松维护，每次插入时只需要前检查$i < x$的$pre[l_i-1]-p[i-1]$的最大值和$i \ge x$的$pre[r_j]-p[j]$的最小值的关系即可。 | ||
2020-2021/teams/alchemist/mountvoom/halltheorem.1589250375.txt.gz · 最后更改: 2020/05/12 10:26 由 mountvoom
