吉司机线段树 1

违规用户名576639 · 2024-10-17 20:14:28 · 个人记录

倒入例题：

给定长为 N 的序列 A，对这个序列做 q 次操作。

第 i 次操作分为如下 2 种情况：

1. 1 l r k 区间取 min。

2. 2 l r 区间求和。

考虑用线段树维护区间总和和区间最大和严格次大值以及最大值出现次数。

对区间取 min 的操作，考虑先在线段树上找到这个区间，那么现在分成了若干个子区间，考虑对这些子区间分别考虑：

1. 如果最大值小于等于 k，并没有影响到线段树记录的信息。

2. 如果恰好只影响到最大值，即严格次大值小于 k 小于最大值，在这里打上标记，这时根据最大值出现次数能快速维护区间和。

3. 同时影响到次大值，考虑往下递归，处理好子节点的答案合并。

在往下递归的过程中，记得下传懒标记。

时间复杂度：O((N + q) \times \log_{2} N)。

时间复杂度分析：

1. 对于每一个结点，看其左儿子与右儿子，接着新建的树上只有其儿子掌管区间最大值较小的结点上点权设为 1，其他结点为 0，特别的根节点在新建的树上点权为 1。

2. 首先在处理区间取 min 的操作中只有 2. 操作和 3. 操作对时间复杂度有贡献，其中显然 2. 操作的贡献为 O(q \times \log_{2} N)，考虑 3. 操作每次往下递归的时候必然会回收一个点权为 1 的点如果没有点权为 1 的点则不会进行 3. 操作，那么这种操作的总时间复杂度为 O(N \times \log_{2} N)。