栈， 队列
P6033
-
操作：找min, 删min, 插入
-
必须线性复杂度
**特殊的性质：每次插入的元素单调递增 **， 即 b 单调
-
两个队列：初始的 a， 合并后的 b, 都是有序的
- 对 a 排序时使用桶排序（快排太慢）
-
总共合并 n - 1 次， 每次 $O(1) $
P2827
- 如果蚯蚓长度不变 -> 普通的优先队列（太慢）
- 特殊性质：最长的蚯蚓在单调递减， 且分成的两段分别单调递减
- 三个队列：原来的 a， px 的 b， x - px 的 c
- 但是长度变化
- 记录全局 tag
- tag += q, 其他实际值不变， 新产生的 -q,
- 再加上三个队列（仍然单调）
- 原来的不变， 新加的原本就比原来的小， -q 后更小
- $ O(n log n + m) $
并查集
P1197
- 正着删边 -> 反向加边
- 时光倒流
P2391
- 线段树可以， 但是时间复杂度太大
- 区间染色
- 正着做会重复染多次
- 所以倒着做
- n 个位置， 每次找到没染色的位置， 就能得到均摊的 \(O(n)\)
- 并查集
- 对于染色的点， 父亲为左侧的点
- 没染色的点父亲是自己
- Find 一次， 找到从右到左第一个没染色的位置
- 只路径压缩， 并查集是接近 $ O(n) $
- 线性并查集
- 将序列分成 log n 大小的块
- 如果块内全是染色的， 就指向其左边的块
- 否则指向自己
- 块内的没染色点设为 1， 可以用类似 lowbit 的位运算 $O(1) $ 找
- 只支持向自己左边连边
线段树
P3373
- 双标记 -> 统一为一个
- 规定一个顺序：先乘后加
- 功能：信息合并， 区间修改， 查询
- 信息合并：
- 信息 + 信息 -> 信息
- 标记 + 标记 -> 标记
- 标记 + 信息 -> 信息
- 信息合并：
- × c + d & × a + b
- (× a + b) × c + d = × ac + (bc + d)
P4513
-
单点修改， 区间查询
- 考虑信息合并
-
维护最大前缀， 中缀， 后缀， 区间和
- 合并后为 c, 原来为 a, b
- c.maxpre = max(a.maxpre, a.sum + b.maxpre) （sum 的用途）
P7706
-
单点修改， 区间询问
-
转化为 找三元组(i, j, k), ai - bj + ak 最大（忽略min bj）
- 三元组全在左边
- 全在右边
- 跨过两个区间（左1右2， 左2右1）
- 左边 ai（区间最大值）， 右边 -bj + ak
- 左边 ai - bj， 右边最大的 ak
- 依赖于 a_max, b_min
- 左边 i 元组， 右边 k - i 元组
P1471
- 维护平方和， 和， 长度
- \(\sum_{i = 1}^{n} (A_i - A_0)^2 = \sum A_i^2 - 2 * A_0 \sum A_i + n * A0 ^ 2\)
- 可以合并
P6327
- 函数
- sin(\(\alpha\)) cos( \(\alpha\)) -> 库函数
P4344
- 维护 0 的前缀， 中缀， 后缀
- opt0 区间全设为0
- opt1 l0 -> r0 设为 0， l1 -> r1 从左到右填 l0 -> r0 个1（二分填的终点）
- opt2 询问最大子段
- $ O(m log ^2 n) $
- （1 个 log？？？？）
P5278
- 找到 min, max
- max - min = (r - l) * k （必要条件， 不是充分条件）
- 区间所有数 % k 相同
- b 是原数组 a 的差分数组
- 等价于 l -> r 为 k 的倍数
- 维护区间 gcd, gcd 应为 k 的倍数
- 没有重复数字
- pre i：i 左边第一个和他相同的数
- pre i < l：无重复数
- 维护区间 pre 的最大值
- 修改时只影响 $ O(1) $ 个 pre
- 对每个值开一个 set 维护下标
- 以上 3 个条件是充要条件
P6617
- 像上一题一样维护 pre[i] 表示 i 前面第一个 w - a[i]
- 但是带修改
- 一个 a[i] 可以对应多个 pre[j]， 修改复杂度很大
- 可以（根号分治？？？）， 但是太麻烦
- 只关心‘存在’
- 有多个 pre 指向一个 a[i], 只把第一个指过去
- 和上一个题类似
// 下午
Codechef DGCD 弱化
- 标记（加法）和信息难以合并（常见难点）
- Gcd 的特殊性质
- 辗转相减法
- gcd(a, b) = gcd(a - b, b)
- gcd(a[l], ......a[r]) = gcd(a[l], b[l + 1]......b[r])， b 是 a 的差分数组
- 区间加 -> 差分数组上单点加 -> [l] + v, [r + 1] + v
T367829
- 最大的《子段平均数》
- 区间长不超过 3
- c 分为 a， b 两部分， 则至少有一部分的平均数 >= c 的平均数， 假设是 a
- 抛弃 b， 保留 a
- 分成 2 和 x - 2 两部分， 则长度 -2 或变成 2
- 100 1 100， 长度可能为 3
- 得出：长度只可能为 2 或 3
- 直接用线段树维护即可
CF280D
- k = 1 最大子段和
- 反悔贪心
- 原来取了的位置允许被删掉
- 去完后所有数都乘 -1 ， 再求最大子段和
- 对该子段取了的部分删掉， 没取的部分留下， 得到一个新的子段
- 如果又去一遍， +1 和 -1 抵消， 相当于没取（反悔）
- 标记合并：乘两次 -1 就抵消了
- 信息合并：小白逛公园
- 标记和信息：整个区间全乘 -1 或 全不变
- 维护两种信息：乘 -1 的信息 和 不乘的（套路）
- (maxpre, maxsuf, maxmid) * 2 套
P3215
-
删掉Swap操作
-
未匹配的括号形如 ) ) ) ) ( ( ( (
-
replace？？？
-
invert 维护 反转后的信息， 没反转的信息（和上一题类似）
P4036
-
删掉操作3
-
线段树 + 哈希 + 二分
-
弱化：单点修改， 查询是否相同
-
线段树维护哈希：$ L * Base ^ {len_r} + R = Root$ $ O(1) $
-
二分匹配的长度
-
$ O(m log ^ 2 n) $
// 均摊问题
经典问题
- 均摊
- x = 1 无意义， x >= 2,
- x = 2 时修改次数最多， 为 log 次
- 每次修改不为 0 的数， 最多 n log n 次
- 问题转化为求第一个非 0 位置的下标
- 线段树 $ nlog ^ 2 n$
- 并查集（上午讲的）$ n log n$
P4145
- 每个数最多开平方有限次 就变成 1 了
- 开平方的次数为 $ log log$ 次
CF438D
-
打标记？
- 不能合并
-
x % p
- x >= p -> x % p
- x < p -> 不变、
- x >= 2p 减半
- p <= x <= 2p 减半
-
取模最多 log 次
-
均摊 $ O((n + m)log V) $
-
找到区间中 >= p 的值的位置
- 每次找区间最大值， 如果 >= p 就对该位置取模， 否则停止执行
-
HDU 6315
- b 是一个排列：$ \sum floor(ai / bi) = n * (1/1 + 1/2 + ... + 1/n) = n * log n $ （调和级数）
- 维护 c 表示还要加多少 ai / bi 发生变化
- 用线段树维护 c
- $ O(n log ^ 2 n) $
P9989
- 性质：
- x 为 ai 的倍数：ai 不变
- 否则 gcd(ai, x) <= ai / 2 （至少变成一半）
- 最多取 log 次 gcd
- 维护 lcm 判断该区间是否有结点不是 x 的约数
- 在线段树上二分， 找一个是 log
- lcm
- lcm = a.mul * b.mul / gcd（a.gcd, b.gcd)
- if lcm > 1e18 -> lcm = 1e18 + 1 （肯定不是 x 的约数）
LOJ 504
- opt1 打一个对 k 取 max 的标记（将 a[i] 与 k 取 max）
- opt2 最小的 x 个数 和 最小的一个数的区别
- 找到区间最小值， 删掉（+1e18）， 再求 x - 1 次
- 删完后加回去
- \(O(\sum x log n) = 2e6 * logn\)
下午总结
- 更复杂的线段树和均摊问题