about 2 years ago

前言

由于吉司机深入研究了线段树,感觉不做几道题会滚粗的。。。

清华集训 V

题目大意:给定一个长度为的初始序列,有以下几种操作:






分析:这道题主要是我们要把标记变成可加的,我们考虑表示,那么前三个操作可以改写成,那么作用于的结果便是,这样我们就可以解决前四个问题了。
考虑怎么求历史最大值,设分别是依次作用在这个点上的标记,考虑历史最大值只有两种形式:


这两个都是可以维护的,如果yy不出来可以去参考一下代码。
时间复杂度
V.cpp

HDU5306

题目大意:给定一个长度为的初始序列,有以下几种操作:



分析:这题主要是从暴力衍生出来的一个思路,然后可以用势能分析证明复杂度是的。
记录最大值,最大值出现的次数,严格次大值,区间和,再加上一个区间取的标记
每次递归到一个结点,设取的值为,分三种情况考虑:
,直接退出;
,修改的值,并且令
,递归到两颗子树里去处理。
HDU5306.cpp

← 最近好懒啊,做了题目不想写题解了。。。 UOJ193:人类补完计划 →
 
comments powered by Disqus