[kuangbin带你飞7]线段树
kuangbin带你飞7
前言
作为一名acm选手,不能连线段树都不会,练就完事了。而且我越发觉得在赛场上不能卡机,中档题才是区分牌子的题目。只有慢慢思索的题目才能真正地提高自己,立下一个flag,每十天完成一个kuangbin专题。现在时间9/6。必须在9/16完成这个线段树专题,就算是困死也得完成。
感想
左右区间还是注意一下,保不准出题人恶趣味。
初始化不能想当然$n$多大树多大,有可能他是一个范围,$n$只是代表着式子的个数罢了。
数组居然还是又一次忘记开4倍。
lazy数组忘记初始化,或者lazy可以为0但是还是初始化为0了。
A.敌兵布阵
题意
这如果我没有记错,应该是人生中第一个线段树题目,很是经典。单点修改,区间查询。
题解
线段树。
AC代码
1 |
|
B.I Hate It
题意
单点修改,区间最值。
题解
线段树。
AC代码
1 |
|
C - A Simple Problem with Integers
题意
区间查询,区间修改。
题解
线段树
lazy需也要开两倍
AC代码
1 |
|
D - Mayor’s posters
题意
贴线段,每次贴都会覆盖掉前面的线。问贴到最后能看到多少种不同的线。
题解
线段树+离散化
覆盖线段的范围是1e8,无法建树所以需要离散化,把线段长度按照排序的顺序重新赋值。由于有$2n$个长度所以记得$maxn$要开两倍。
区间修改,单点查询。
AC代码
1 |
|
E - Just a Hook
题意
区间修改,区间查询
题解
线段树
ac代码
1 |
|
F.Count the Colors
题意
在一条线上区间涂颜色。
问所有颜色出现的区间块的数量。
题解
线段树+懒惰标记
需要注意的是,$n$不代表着数据的范围,8000才是数据的范围,并且由于区块间有空隙,所以离散化还有点不好做。虽然数据也只有8000。注意的是初始化的范围要覆盖到8000,不能以为到$n$就好了。
+5 $n$当坐范围
+3 误以为build函数能够初始化所有的点,但其实是要memset(vis,-1,sizeof(vis));
AC代码
1 |
|
G.Balanced Lineup
题意
求区间最大值和最小值的差
题解
可以用ST表预处理,也可以用树状数组或者是线段树,线段树的常数比较大,但他们的复杂度均是$O(nlogn)$
AC代码
1 |
|
H.Can you answer the queries?
题意
区间数字根号,区间查询数字和。
题解
线段树+智力门槛
因为所有数字最多根号8次就会变成1。所以我们只需要处理一下当数字为1就不用再更新区间内的数了。
acm还是靠智力和眼力啊,我想了半天都没想出来什么数学方法,原来只需要看出规律和找到最关键的突破点就ok了。
+1超时忘记开4倍数组了。。
+1 虚伪的看到了提醒要注意l,r的大小关系,妈的,这都卡,是不是人啊。
AC代码
1 |
|
I Tunnel Warfare(前面写过了)
题意
题解
ac代码
1 |
|
J.Assign the task
题意
dfs序+线段树模板题
题解
同上
+1 lazy数组没有初始化,没适应无build建树
AC代码
1 | #include<bits/stdc++.h> |
K.Transformation
题意
有四种操作。
- 将$[l,r]$区间的数字加上$val$.
- 将$[l,r]$区间的数字乘上$val$
- 将$[l,r]$区间的数字变成$val$
- 求区间$[l,r]$内所有数字$[1,2,3]$次方的和。
题解
线段树
对于线段树的懒惰标记和取模运算细节要求很高。
相信对于sum数组的转化大家都能够推得出来,但是关于pushdown的操作是另有玄机。
首先他的顺序很重要。得先将lazy[1]递推下去,也就是操作3把数字变成$val$,之后再进行乘法和加法的操作。对于乘法很重要的一点是你在lazy[2]标记递推的时候,其实你把子树中的加法也相当于乘了$val$,所以递推不仅要递推乘法标记,还要递推加法标记。
+3 更新Pushdown中你也要更新lazy数组的值
+1 更新的次序也有关系
+1初始化 有的要1.
+1 少写一个|1 rt[rt<<1|1]写成了rt<<1
+10000 有一个r-l+1写错了,下次写成 len 。不然很容易出错妈了个鸡
AC代码
1 |
|
L - Vases and Flowers
题意
做过 在我之前博客里面有。
题解
做过
+2 忘记掉可能初始不能放在A点,所以要加入一个全局变量flag,初始化maxl。
AC代码
1 |
|
M - 约会安排
题意
对每一次查询寻找$val$长度的最前面空闲时间并占据他。
- 如果是女神来查询,那么空闲的时间也包括基友的时间
- 如果是基友来查询,那么只有空闲的时间可以选择
- 如果想要学习$[l,r]$,那么$[l,r]$之间的时间都会被清空。
题解
线段树的区间合并。
这里由于要维护两个线段树,所以用结构体来构造树,不过确实使用结构体封装之后复用性高了很多。
- 定义三个量$ll,rr,mm$分别表示从区间$[L,R]$最左边开始的最长长度和从区间最右边开始的最长长度和区间内横跨中点的最长长度。
- 定义$maxlen$来表示区间内最长的长度来剪枝。
这样就可以更新了。
一棵树代表屌丝+女神占有的,一棵树代表女神占有的。
查询分为三种方向
- 先查询左边开始的长度是否大于$val$,如果大于返回$L$,或者是递归左子树。
- 再查询中间的部分长度是否大于$val$,如果大于返回$mid-rr[lc]+1$就是中点减掉从左半部分右边的长度。
- 再查询递归右子树。
+1 区间合并中 更新父节点必须每个都更新,所以有时候你在return 之前也要更新一下。
AC代码
1 |
|
N.picture
题意
求多个矩形周长的并
题解
扫描线+线段树
这道题目没有离散化$X$坐标就可以做。而且例子也只有一个。。
ac代码
1 |
|