1,844 views

线段树学习记录?

posted in: 学习记录 | 15

最近学习了线段树的新技巧。大体上就是通过一些分析来证明在某些地方暴力后复杂度仍然有保证。

 

[codeforces \ \#250 \ div1 \ D. \ The \ Child \ and \ Sequence]

给一个序列,要求支持的操作:

1.区间取模。

2.单点加。

3.区间求和。

1 \le n,m \le 10^5

Tutorial

注意到对区间取模很麻烦,也不能通过打标记来解决问题。

首先对于一个比模数p小的x, x % p =x。(废话)。那么就不用取模啦。

并且取模有很好的性质:

这意味这对一个数取模后这个数至少会/2。

所以一个数最多会被取模loga_i次。

那么我们可以维护区间[l, \ r]的最大值。对于一个模数p,如果区间所有数都比p小,这个区间就保持不变。

否则就一直做下去直到满足条件或 l = r.

复杂度O(n \ logn \ loga_i)

 

 

[uoj \ \#228] 基础数据结构练习题

给一个序列,要求支持的操作:

1.区间加。

2.区间开根。

3.区间求和。

继续考虑区间开根的操作。

首先对于两个相邻的数,i和i+1,他们的平方根只有两种情况:

1.sqrt(i) = sqrt(i+1)

2.sqrt(i) + 1 = sqrt(i+1)

那么我们考虑对于区间[l, \ r]维护最大值和最小值,如果我们遇到了mx = mn + 1的情况,那么

1.如果他们的sqrt相等,设为A,那么相当与整个区间覆盖为A。

2.他们的sqrt为A和A+1,那么相当于每个数减去了(mn - A)。(即mx - (A + 1))

 

如果mx \neq mn +1那么一直做下去,直到满足条件或 l = r。

这样复杂度是怎么保证的呢?线段树某区间中相邻的两个数,每次开根他们之间的差值都会减少,大概开个5次就差会变为1。

大概是O(n \ log \ n)再带一个常数。

 

 

[udp 9.4]

[codeforces \ \#FF \ div1 \ C \ DZY \ Loves \ Fibonacci \ Numbers]

给一个序列,要求支持的操作:

1.区间加斐波那契数。

2.区间求和。

1 \le n, m \le 300000

orz...

考虑线段树上tag的合并。由于两个斐波那契数列加记起来还是斐波那契数列,那么我们只要维护前两项a,b即可。

即 a, b, a + b, a + 2b,2a + 3b...

观察可知第n项f[n] = a * fib[n - 2] + b * fib[n - 1],其中fib是以1 1为前两项。

而怎么求f的前n项之和呢。

f[n] = f[n - 1] + f[n  - 2]

f[n - 1] = f[n - 2] + f[n - 3]

....

f[4] = f[3] + f[2]

f[3] = f[2] + f[1]

左右累加可得

f[n] - f[2] = \sum_{i=1}^{n-2}{f[i]}

所以\sum_{i=1}^{n}{f[i]} = f[n + 2] - f[2]

那么就可以维护了。

 

题解里提供了奥妙重重的做法...转化成了区间加等比数列。维护起来差不多。

等比加等比还是等比数列,求和的话套公式就好了。LINK

 

 

//继续沉迷屁股药丸

[upd 9.7]

[spoj \ KQUERYO]

询问区间l, r内比k大的数的个数。

1 \le n \le 30000

1 \le q \le 200000

膜了zkx学到了不用主席树的姿势。

每个节点存一发vector,记录了包含区间的a_i已排序好的顺序。

查询时直接二分就好了。STL使用练习。

复杂度最坏O(nlog^2n)。拿来偷懒还是不错的QQ图片20160907200520

听说做题要先看评论?

[upd 12.10] \#164. 【清华集训2015】V

1. 1 l \; r \; x[l, r]中的数加x

2. 2 l \; r \; x[l, r]中的数减x, 并对0取max

3. 3 l \; r \; x[l, r]中的数覆盖为x

4. 4 y 询问该位置当前值

5. 5 y 询问该位置历史最大值

学习了赛格蒙特比鮆的简单姿势,用来处理一些带历史询问的问题。

首先每个修改都可以看成加上一个数,再对一个数取max。

那么每个修改就分别是(x, 0) (-x, 0) (-INF, x)。

可以看出这是一个分段函数。标记(a, b)和(c, d)合并后会变成(a + c, max(b + c, d))

历史标记则是记录对于每个数x, f(x)能到的最大值,也可以类似的维护。

注意每次下传标记要先传历史标记再传现在的标记。

http://uoj.ac/submission/112798

 

[upd 1.17]

下午听吉利大爷讲了一波数据结构,感觉学会了许多姿势,吉利爷好劲啊!

 

感觉终于学会了线段树合并的姿势,以前根本不知道这东西的复杂度是怎么证的。

由于动态开点,一开始有O(nlogn)的节点

每次合并花费1代价减少1个节点,最后会剩下O(n)个点,所以总复杂度是O(nlogn)

bzoj 4530 [Bjoi2014]大融合

每次动态插入一条边,询问一条边两边的联通块大小。1 \le n \le 100000

我们可以先dfs出每棵树,那么要求的就是某棵子树的size大小,和当前联通块大小

对于求子树size大小,可以转化为dfs序+线段树

于是就可以上线段树合并啦

当然了,这题难道不是一眼LCT?

 

(感觉还学到了许多姿势,没地方切?)

15 Responses

  1. cicada的小粉丝

    劲啊!

  2. 劲啊!

  3. cicada的小粉丝

    劲iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiing啊!

  4. Cicada的小小粉丝

    劲啊!!!!!

  5. 大家好,我是cicada,我是你们的红太阳!至于为什么不用大号发这条评论,嗯...大爷的心思岂是你们能胡乱忖度的?

  6. 楼上 loves CC

  7. 大家好,我是cicada,我是你们的红太阳!至于为什么不用大号发这条评论,嗯...大爷的心思岂是你们能胡乱忖度的?

  8. 大家好,我是AwD,我是你们的红太阳!至于为什么不用大号发这条评论,嗯...大爷的心思岂是你们能胡乱忖度的?

  9. 大家好,我是AwD,我是你们的红太阳!至于为什么不用大号发这条评论,嗯...大爷的心思岂是你们能胡乱忖度的?

  10. ch的小粉丝

    催更!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Leave a Reply