Tag Archives

2 Articles

OI

[Fortuna OJ]4606 – 序列 / HEOI 2016 Sequence

Posted by kal0rona on

主要思路

由于本人分治很菜,所以就来刷分治题了。

先思考 50 分\(O(n^2)\)的做法。记录每一个位置的原始值、变化后的最大值、变化后的最小值,然后发现如果一个位置\(i\)对后面的位置\(j\)有贡献当且仅当:

\[a_i < minVal_j \ (1) \\ maxVal_i < a_j \ (2) \]

所以这就相当于一个二位偏序的题目,有两个限制。我们可以用整体二分,在做完左区间之后,左区间按原来的值进行排序,而右区间按最小值进行排序,即可满足第一个条件;第二个条件可以用线段树来搞,搞两个指针来比较大小,然后用线段树来统计答案即可。非常好写。