A – 礼物
sb 暴力出奇迹,欺骗人的感情。
敢情您特么\(1e9\)的复杂度都能过?真的服气。
由于本人分治很菜,所以就来刷分治题了。
先思考 50 分\(O(n^2)\)的做法。记录每一个位置的原始值、变化后的最大值、变化后的最小值,然后发现如果一个位置\(i\)对后面的位置\(j\)有贡献当且仅当:
\[a_i < minVal_j \ (1) \\ maxVal_i < a_j \ (2) \]
所以这就相当于一个二位偏序的题目,有两个限制。我们可以用整体二分,在做完左区间之后,左区间按原来的值进行排序,而右区间按最小值进行排序,即可满足第一个条件;第二个条件可以用线段树来搞,搞两个指针来比较大小,然后用线段树来统计答案即可。非常好写。