以前并没有刷过 kuangbin 专题,ICPC 南京站赛前 20 天系统刷两三个专题吧,这篇是线段树。
ZOJ1610 Count the Colors
题意:区间染色,问最后从上面看到每种颜色有多少段。
分析:线段树区间修改,flag
维护区间颜色;统计答案时,暴力扫描,单点查询颜色,只要当前点的颜色和前一个点不一样,该颜色段数++。
|
|
HDU1540 Tunnel Warfare
题意:有 $n$ 个点连成一条线,编号从左至右为 $1\text{~}n$,有三种操作:① 摧毁一个点 ② 查询某个点能到的所有点数(包括自己) ③ 重建上一次被摧毁的点。
分析:用一个栈 stk
来存放被摧毁的点,摧毁点 x
就 stk[++top] = x
,重建上一个点就只需要取出栈顶 x = stk[top--]
。线段树每个节点维护区间左侧连续最大长度(点数) lmax
以及右侧最大连续长度 rmax
。摧毁一个点就是在线段树中找到该点并将其 lmax=rmax=0
,重建就是 lmax=rmax=1
,然后 pushup
上去。难点在于②号查询操作,如果点 x
在当前结点的左孩子,分两种情况来看,如果点 x
被左孩子的右侧最大连续区间包含了,那么 x
能到达的所有点数就是左孩子的 rmax
+ 右孩子的 lmax
,否则递归直接递归左孩子即可。剩余情况类似。
|
|
HDU3974 Assign the task
题意:给定一棵 $n$ 个点的树,有点权,有两种操作:① 将子树 x
置为同一个数 ② 单点查询某点权值
分析:DFS
序 + 线段树。子树 x
转化到 DFS
序中的区间 [dfn[x], dfn[x] + sz[x] - 1]
。然后就是水题了。
|
|
HDU4578 Transformation
题意:线段树区间加,区间乘,区间置数,区间和,平方和,立方和。
分析:写吐了。。需要维护,置数标记 same
,乘法标记 mul
,加法标记 add
,区间和标记 s[0~2]
分别表示和,平方和,立方和。
首先确定前三个标记维护优先级,same
> mul
> add
,然后就是三个和的维护需要推导一下。
- 区间置数,三个和很好维护不说了。
- 区间乘 $k$,三个和分别乘以 $k,k^2,k^3$
- 区间加 $a$,初始有 $s[0]=\sum{x}$, $s[1]=\sum{x^2}$, $s[2]=\sum{x^3}$,区间长度为 $len$$$\sum{(x+a)}=\sum{x}+\sum{a}=s[0]+len*a$$$$\sum{(x+a)^2}=\sum{x^2}+2a\sum{x}+\sum{a^2}=s[1]+2a*s[0]+len*a^2$$$$\sum{(x+a)^3}=\sum{x^3}+3a\sum{x^2}+3a^2\sum{x}+\sum{a^3}=s[2]+3a*s[1]+3a^2*s[0]+len*a^3$$注意维护和的时应该倒序维护(立方和,平方和,和),防止要用的值被先更新了。
|
|
HDU4614 Vases and Flowers
题意:编号为 $0\text{~}n-1$ 个空花瓶从左至右摆放。两种操作:① 将区间 $[a, b]$ 花瓶中的花全部清空并输出清空了多少束花 ② 给你 $b$ 束花,从花瓶 $a$ 开始往右,遇到空瓶子就插一束花。输出一个区间:[第一个插入的位置,最后一个插入的位置]。
分析:不妨编号向右偏移 1 个单位。线段树维护两个 lazy 标记,same
标记区间全 1 或者全 0,或者没有意义,sum
标记区间内有多少束花。操作 ① 区间置 0 即可吗,操作 ② 利用维护的 sum
值先二分起始位置(找到第一个空瓶子),然后二分结束位置(找到恰好插完第 b
束花的位置,注意 b
应该先与空瓶子数取 min)。
|
|
HDU4553 约会安排
题意:好麻烦不写了。
分析:线段树维护两个时间轴的信息,分别表示屌丝时间轴的分配情况,还有女神时间轴的分配情况。详见代码,下标 0 表示屌丝,下标 1 表示女神。same
为区间相同的值的标记,lmax, rmax, tmax
分别表示区间左侧最长连续空闲时间,右侧最长连续空闲时间,区间内最长连续空闲时间,用 1 表示空闲。然后根据题目要求操作即可,代码中相关注释应该比较清楚。
|
|
HDU1542 Atlantis
题意:线段树扫描线求矩形面积并。
分析:注意线段树的每一个叶子结点表示的不是单个点,而是一个区间,其中的标记含义如注释。
|
|
HDU1255 覆盖的面积
题意:线段树扫描线求至少被覆盖 2 次的矩形面积并。
分析:与上一个题目类似,这里需要分别维护 len1, len2
,其中 len1
含义与上一个题的 len
一样,len2
表示线段树区间内被覆盖至少 2 次的实际区间的合并的长度。只需要求改 pushup
函数,更新 len2
时候需要分情况讨论,如果区间被完全覆盖了至少 2 次,len2
就是区间长度;否则,如果当前是叶子结点,那么此时最多会被完全覆盖 1 次,对 len2
没有贡献;否则,如果不是叶子结点并且恰好被覆盖 1 次,那么想要求该区间内至少被覆盖 2 次的长度,就需要计算当前结点的左右子结点中被覆盖至少 1 次的长度,如果不是叶子结点并且没有被完全覆盖过,直接用子结点的 len2
之和来更新当前结点的 len2
即可。有点绕,但是并不难理解。
|
|
刷一遍感觉码力变强了qwq(错觉x.