卧薪尝胆,厚积薄发。
Gorgeous Sequence
Date: Fri Feb 15 18:56:57 CST 2019
In Category:
NoCategory
Description:
区间取
$\min$
,区间求和,区间求
$\max$
。
$1\leqslant n\leqslant 10^6$
Solution:
吉司机线段树模板题,线段树每个点维护最大值
$fi$
,次大值
$se$
,最大值个数
$cnt$
和区间和
$sum$
,然后每次修改如果大于等于区间最大值就什么都不做,如果小于最大值大于次大值,就利用
$cnt$
更新
$sum$
并打一个
$tag$
退出,否则暴力
$dfs$
子树更新答案,这样做的复杂度是
$O(n\log^2n)$
的。
Code:
In tag:
数据结构-吉司机线段树
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡