小清新线段树

小清新线段树的概念是由jiry_2提出的,区别于zkw(重口味)线段树命名。这里我的理解是可以归为一类结合时间复杂度分析以及懒标记应用的非传统线段树。不过既为非传统,这类题目总体来说还是做法各异,下面就结合题目做一些分析。


入门难度

1.bzoj 3211 花神游历各国

区间求和,区间开根号(下取整)

因为只有开根号操作,所以最后不是1就是0,且一个数开根号次数\(O(loglogC)\)级别的,1e9的数最多开5次。所以就怎么暴力都行了,比如判断当前区间最大值是否是1,或者直接记录访问每个节点的次数是否达到5次,用于剪枝。时间复杂度\(O(nlogn+nloglogC)\)。

2.bzoj 3333 排队计划

这个题其实不是很入门

有一个排列,每次修改是给一个位置x,先拿出x及之后所有小于等于a[x]的数,从小到大排序后,再放回空位中,一开始及每次操作完都要输出当前排列的逆序对数。

计算逆序对数就用传统方法,把以每个位置为开头的逆序对数加起来。那么通过观察发现,这个排序操作会抹掉x及之后所有小于等于a[x]的那些位置的贡献,并且不会对其他不动的位置的贡献造成影响。这样每次用线段树通过判断最小值,每次暴力下去找到需要清除贡献的地方即可,因为每个点只会被清除一次,那么平摊下来总时间复杂度就是\(O(nlogn)\)。

 


进阶难度

1.Petrozavodsk Winter-2018. AtCoder Contest I. ADD, DIV, MAX

维护序列,支持区间加,区间整除,区间求最大值。

我们定义线段树上每个节点势能函数为\(W=log_2(Max-Min)\),或者直观理解就是这个区间除以多少次2就会完全相同。那么由于线段树一共\(O(n)\)个节点,初始总势能为\(O(nlogC)\)。因为线段树区间操作会访问\(O(logn)\)个节点,所以一次区间加操作至多增加\(O(lognlogC)\)。由于我们修改时访问一个节点就会使该节点势能减一,所以总的时间复杂度是\(O(nlognlogC)\)。

具体实现就是线段树维护最大值最小值,以及加法的懒标记,对于除法操作如果当前区间的最大值和最小值的改变量是相同的,那么对于这个区间来说,除法操作就可以看成整体加上一个数,否则暴力递归到左右子树。

2.Codeforces 438D The Child and Sequence

维护序列,支持区间求和,区间模一个数,单点修改。

首先需要用一个很好证明的式子\(x\quad mod\quad p<=\frac{x}{2}\),也就是说模操作会让每个数至少除以2。由于只有单点修改,那么就比上一个题好分析了,势能函数是每个区间最大值除以2的次数,初始总势能\(O(nlogC)\),单点修改还是,改变了\(O(logn)\)个点,每个点充能\(O(logC)\),所以总的时间复杂度\(O(nlognlogC)\)。

那么具体实现额外维护最大值,当区间最大值小于模数就剪枝,否则暴力下去。

3.hdu 5306 Gorgeous Sequence

维护序列,区间对一个数取min,询问区间最小值,区间求和

这个题的做法就比较科幻了。

《Segment tree Beats!》课件中关于时间复杂度的证明一些是错误的

可以参考这里,http://jiry-2.blog.uoj.ac/blog/1404

时间复杂度\(O(nlog^{2}n)\)。

 

4.hdu 5634 Rikka with Phi

维护序列,区间赋值,区间取phi,区间求和。

首先根据定义以及相关公式,知道一个大于2的正整数的欧拉函数都是偶数,一个偶数的欧拉函数就至少小了一半,那么一个数能做的次数也就是\(O(logC)\)级别的。

根据前面几个题,这个题的操作就很好想了,如果当前区间的数都相同,那么区间取phi的操作就转化成了区间赋值,同样的打标记即可,不同的话就暴力下去。

时间复杂度是一个log的就比较确信了,然而并不会证。

 

线段树优化凸壳

Lena and Queries

题目链接:http://codeforces.com/contest/678/problem/F

三种操作,1.插入一个点(x,y) 2.删除之前第i个操作插入的点 3.给一个q,询问在已有点中qx+y最大是多少

如果没有删除完全可以cdq分治然后在上凸壳上三分。有删除操作的话因为贡献不独立,所以不能cdq分治。

但是可以用上一次线段树优化建图一样的技巧,按时间来看,因为每个点的存在是一段区间,那么就可以用线段树拆成log个区间,然后把点“打”在上面(加进vector),最后对于线段树上每个区间,做凸壳然后询问就行了。每个询问会被问log次,所以时间复杂度粗略算有\(O(nlog^2n)\)。

 

 

线段树优化建图

有一类经典的问题,之前见过很多次了,好像某一场区域赛的热身赛里就出过:一维数轴上有n个炸弹,\(x_i,r_i\)分别表示第i个炸弹的位置和引爆半径,即如果引爆炸弹i,那么位置在\([x_i-r_i,x_i+r_i]\)范围内的炸弹都会爆炸,并且引发连锁反应。然后比如询问最少引爆几个炸弹才能全部炸完。

首先一个建图思路是如果i能引爆j,那么i向j连一条边,做tarjan求强连通分量就可以知道很多信息了。但是这样暴力连边是\(O(n^2)\)的,需要优化。一个显然的观察是,一个点i的引爆范围是一段区间(这句是废话),所以是和一个区间的点连边,那么我们把炸弹按位置排序后,1到n编好号,建线段树,线段树每个点向左右儿子分别连边。如果i要向区间(l,r)所有点连边的话,就在线段树中将区间(l,r)分解成\(O(logn)\)条线段,这样就转化成了向对应的线段树中的一些点连边,总的边数就是\(O(nlogn)\)。

来看两道具体的题目:

bzoj 5017 [Snoi2017]炸弹

询问如果把第 i 个炸弹引爆,将引爆多少个炸弹。

线段树优化建图,然后tarjan,答案是从i所在的SCC出发,能走到的SCC含有的原炸弹数之和。因为对于每个i都要询问,所以这里不能暴力,一个方法是在这个DAG的反图上拓扑序dp一下。

 

Petrozavodsk Winter-2018. Carnegie Mellon U Contest A Mines

现在每个炸弹多了一个初始的引爆费用,因为连锁发生的爆炸是免费的。有q次修改,每次修改一个炸弹的费用,对于每次修改都要查询当前要引爆所有炸弹的最小花费。

前面的操作都一样,首先一个显然的想法是只要引爆DAG中所有入度为0的SCC里的费用最小的炸弹。然后有个致命的问题是,入度为0的SCC可能不含有原1到n号点,所以需要做拓扑排序删掉没用的点,之后对于每次询问用set维护即可。