洛谷5029 - T'ill It's Over

做那么多水题,会不会被婊…

还是网络流,只不过这次我们需要从一个区间连到另一个区间,那么就是个典型的线段树优化建边。
需要注意一些小细节。

洛谷4839 - P哥的桶

每个点维护线性基,线段树的两个子节点合并的时候直接把一个点的暴力插入到隔壁即可。

BZOJ5405 - platform

首先,我们需要知道如何利用后缀数组对一个指定的字符串计算字典序 Rank 。我们以 abaab 为例:

1
2
3
4
5
6
7
8
9
10
 a    a    b
11 10 9
a b
x 8
a b a a b
x x 7 6 5
b
4
b a a b
x 3 2 1

按照顺序进行编号,因为本质相同的字符串不重复计算次数,所以每一行的前 $height_i$ 个不计入个数,所以我们也有了一个很自然的 $O(n ^ 2)$ 做法。

接下来我们考虑正解,可以发现,每次可以看做对上面的字典序 Rank 数组进行了依次递减的区间覆盖,可以使用线段树维护。同时我们可以发现,这个 Rank 是递减的,而前缀和是递增的,所以我们可以二分出相等的那个位置。

这题需要用到一个惯用的套路。

$$a - b \leq |a - b|$$

显然如果是 $a - b$ 非负的,直接取等号;如果 $ a - b $ 负数,那么绝对值就是正数,负数一定小于正数。

考虑到 $ 2 ^ 5 ​$ 并不是很大,我们可以暴力枚举每个数的符号(用状态压缩的方式)。然后维护一棵线段树进行修改和查询即可。

本题有虚树做法,基本思想差不多,但个人感觉还是换根树剖清真一点 233。

定义一组询问的根节点为这组询问的一号节点。

一个点会对答案产生贡献,当且仅当这个点到这组节点的其他节点的距离大于等于这个节点到这组询问的根节点的距离。

假设当前我们做到根节点为 $ root $ ,当前节点为 $ u $ 的情况,找出这条路径的中点为 $ mid $ ,那么肯定不会对答案产生贡献的点即整颗树 $ root $ 为根节点时 $ mid $ 这个节点的整颗子树。就是一个简单的换根树剖,乱搞一下即可。

考虑离线做法,每个物品存在的时间一定是一段连续的区间。建一棵线段树按时间分治,乱搞一下。

考虑在线做法:有一个部分分是只会在一端进行插入删除操作,那么我们开个栈,插入元素就加进去,删除就弹出。复杂度 $ O ( n m ) $ ;既然我们需要在两端操作,那么我们只要维护两个这样的栈即可,查询时把两边的 dp 数组合并。暴力合并是 $ O ( m ^ 2 ) $ 的,会 TLE ,所以我们把一个数组放在线段树上,枚举另一个数组的每一个数,做一下区间查询即可。同时有个问题即有可能在前端删除从后端插入的元素,这种时候我们暴力重构两个栈,各放一半的元素,就能保证复杂度。最后总时间复杂度 $ O (n \log n \times m \log m) $ ,可以通过此题。

由于笔者在做题时把合并的 $ O (m ^ 2) $ 算成了 $ O ( m ) $ 所以去写了在线做法,还好想出了线段树才捡回一条命 233。

按题意可知,考虑每个节点会给左孩子带来一个 $(-\infty, a_i )$ 的限制,会给右孩子带来一个 $(a_i, +\infty)$ 的限制。 定义限制 $(-\infty, a_i)$ 的限制取反为 $(a_i, +\infty)$ ,反之亦然。

考虑把原树进行树链剖分。每个节点存放自己给重儿子带来的限制,用支持单点修改、区间取反、区间查询的线段树维护区间限制的并集。由于每个节点往上跳只会经过 $\log n$ 条重链,重链内部直接从线段树上查询,两条重链之间的转移把转折点对重儿子的限制取反即可。总复杂度为 $O(n \log ^ 2 n)$,可以通过此题。

为什么这题的名字这么奇怪?
为什么这题的题解都是分块?

好,我们讲怎么用线段树做:
首先先把 $1$ 和 $2$ 两个操作用线段树维护出来(这很简单),至于排序我们直接统计区间内每个字母的数量(用操作 $1$ ),然后再直接放回去即可(用操作 $2$ )。

以及这题大小写字母都会出现,无视即可。

时间复杂度 $O(n \log n \times 26)$

给定一个序列,要求兹滋: 区间加数、区间除以数、区间求和、区间求最小值。

其他都很简单,关键在于怎么解决区间除法。

一开始很容易想到之前的 “花神游历各国” ,但是这题并不能这样做(有区间加数),感觉线段树不可做想分块然而分块照样没法解决除法的问题。

正解则是将除法转换为减法,如果当前区间的最大值和最小值与除以除数的数的差值相同,那么把除数变成减数。

复杂度为 $O(n \log^2 n)$ 据称可以用势能分析,但是本蒟蒻太菜了不会,因此略过 QAQ。

已知每个数最多能被开方而减小的次数是有限的,当当前的数是 $0$ 或 $1$ 时就没有必要操作。

所以我们可以用线段树维护区间最大值,如果当前的最大值已经等于 $0$ 或 $1$ ,就无需操作,否则逐个修改。

复杂度 $O(n \sqrt {10^9} \log n)$ ,可过。

区间取模操作同理。

理论上来说资瓷区间开方 / 取模和单点修改,算是优美的暴力吧。


多倍经验(数据范围和要求略有不同):

  1. BZOJ3211 - 花神游历各国
  2. 洛谷4145 - 上帝造题的七分钟2 / 花神游历各国
  3. SPOJ2713 - GSS4 - Can you answer these queries IV

本题的 $n$ 特别大,如果直接开那么大的空间,想必会直接超时。所以我们可以先把所有“用户”合并成一个点,需要访问到哪个就进行分裂。这样的话 $m$ 次操作每次都只会分裂一次,时间复杂度就能保证在 $O(m\log m)$ ,空间也不会炸。

另外本题只有提到最前面和提到最后面两种操作,使用平衡树的必要不大,用动态开点线段树就好了。

p.s. 感觉 Leafy Tree 和这个好像啊 (=’w’​=)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×