2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training9
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training9 [2021/06/20 21:32] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training9 [2021/06/20 21:37] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| $$ | $$ | ||
| - | 不难用线段树维护求解 $g(i)$，接下来考虑贪心逐位求最小和最大字典序单峰序列。 | + | 不难用线段树维护求解 $g(i)$，另外最长单峰序列长度为 $\max(g(i)+f(0,i)-1)$。接下来考虑贪心逐位求最小和最大字典序单峰序列。 |
| 最小字典序只需要从前往后考虑找到第一个满足相应条件的位置。 | 最小字典序只需要从前往后考虑找到第一个满足相应条件的位置。 | ||
| - | 考虑当前是否已经强制降序，通过 $f(1,i),g(i)$ 判断选取当前位置的数后是否可以构造最长单峰序列即可，时间复杂度 $O(n)$。 | + | 考虑通过当前是否已经强制降序，以及 $f(1,i),g(i)$ 判断选取当前位置的数后是否可以构造最长单峰序列即可，时间复杂度 $O(n)$。 |
| - | 最大字典序需要从后往前考虑找到第一个满足相应条件的位置，但需要保证每个数只被扫到 $O(1)$ 次，用桶维护即可。 | + | 最大字典序需要从后往前考虑找到第一个满足相应条件的位置，和最小字典序类似，但需要保证每个数只被扫到 $O(1)$ 次，用桶维护即可。 |
| 总时间复杂度 $O(n\log n)$。 | 总时间复杂度 $O(n\log n)$。 | ||
2020-2021/teams/legal_string/jxm2001/contest/2021_buaa_spring_training9.1624195921.txt.gz · 最后更改: 2021/06/20 21:32 由 jxm2001
