2020-2021:teams:alchemist:mountvoom:halltheorem
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:mountvoom:halltheorem [2020/05/12 10:23] mountvoom |
2020-2021:teams:alchemist:mountvoom:halltheorem [2020/05/12 10:29] (当前版本) mountvoom |
||
|---|---|---|---|
| 行 25: | 行 25: | ||
| $\forall 1\le i< j\le n,[i,j]\text{中被选择的右侧点个数}\le [l_i,r_j]\text{中左侧点数量}$ | $\forall 1\le i< j\le n,[i,j]\text{中被选择的右侧点个数}\le [l_i,r_j]\text{中左侧点数量}$ | ||
| + | 令$pre[i]$为$a[i]$的前缀和，$p[i]$表示$[1, i]$中已经被选择的右侧点的个数，公式等价于： | ||
| + | |||
| + | $\forall 1\le i< j\le n, p[j]-p[i-1]\le pre[r_j]-pre[l_i-1]$ | ||
| + | |||
| + | 即: | ||
| + | |||
| + | $\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]$和$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.1589250229.txt.gz · 最后更改: 2020/05/12 10:23 由 mountvoom
