P6242 [模板]线段树3
线段树3汗
吉如一线段树
对于一个区间取min,我们显然没法直接做,因为有些是没法取min的,有些是会发生变的
所以考虑直接递归左右子树
这里我们显然有一个剪枝,就是如果区间最大值小于当前的min操作,就不进行
然后加上这个还不太够,我们再来一个区间次大值
如果min操作在次大值和最大值之间,我们不递归直接减少最大值,发现需要维护一个最大值的个数
如果min操作小于次大值,直接递归子区间
因为你会发现这样我们每次min操作至少有两个数会变得相同qwq那么进行n次操作就会使得所有数都相同了,然后就可以使得我们之后的取min操作快的一比
同时区间和很好维护,区间max也很好,区间min也很好维护
这道题就做完了,注意一个加法标记,他的优先度最高了,然后我们因为第二个操作直接减少了最大值,那么还需要一个区间min标记,表示这个区间取min了,也很简单,你会发现我们min标记不可能引起递归
然鹅你会发现我们还有一个操作5,噩梦....
我们会发现如果合并会导致函数段数无限增长,就是考虑一个先加后取min或者取max的操作
如果我们维护最大值取max
这个加法和这个取max兼容之后得到的最大值结果
但是如果取min,我们最大值会这样变化
这个我们维护最大值修改的历史最大值就好了额,相当于删掉了这个交点之前的信息
这样子就做完了这道题QAQ但是标记合并的时候要有整整将近10个标记要合并