【听课记录】25.10-LCA-Week5

· · 个人记录

10.22 数据结构

CF444C DZY Loves Colors

题意

有长为 n 的序列 a,b，初始 a_i=i,b_i=0。操作对一个区间 [l,r] 内的 i 进行 b_i\leftarrow b_i+\left|a_i-k\right|,a_i\leftarrow k 的修改，查询 b 的区间和。n,m\le 10^5,k\le 10^8。

题解

由于 a 有不同，对 a 覆盖时 b 的变化量不同，难以直接维护。然而区间覆盖是破坏性操作，会使得这段区间之后一直相同，可以使用势能线段树或颜色段均摊解决，前者即只对线段树上颜色相同的节点操作。

至于颜色段均摊，考虑维护 a 序列所有极长连续相等段，每次只对整段操作，显然原来相等的 a 得到的贡献相等，可以区间加解决。之后把 [l,r] 变成新的一段。若有 k 个段被完全包含，则会进行 (k+2) 次区间加，且段数减少 (k-1)，于是区间加的总次数不超过 3n+q。使用线段树或树状数组维护区间加区间求和即可，复杂度 \mathcal O((n+q)\log n)。

CF1638E Colorful Operations

区间赋值操作启发我们使用 ODT。对于每种颜色再维护一个标记，元素被改变颜色时处理一下标记贡献的改变即可，大概是区间加单点求值，上树状数组就行。之后应该会写。

CF453E Little Pony and Lord Tirek

题意

每个位置有初始值 s_i，上界 m_i，单位时间的增加量 v_i。进行 q 次操作，在经过一段时间后求区间 [l,r] 内所有值的和并将其清空。n,q\le 10^5。

题解

若上次清空到求值经过了 t 单位时间，当前值为 \min(m_i,tv_i)，分讨 \lfloor\frac{m_i}{v_i}\rfloor 和 t 的大小关系即可。注意到贡献只跟 t 有关，于是考虑按上次清空时间进行颜色段均摊，这样每段内的 t 相等，容易计算贡献。这样变成若干段区间的 \min(m_i,tv_i) 之和，根据 \lfloor\frac {m_i}{v_i}\rfloor 离线扫描线即可解决，复杂度 \mathcal O((n+m)\log n)。

P5066 [Ynoi Easy Round 2014] 人人本着正义之名

可以发现向前后位运算本质是一些连续的连续段内某一种段长度增长，另一种长度减短，使用平衡树维护所有连续段并打标记即可。为了防止段缩没，还需要记录区间内最短的两种区间长度，当出现长为 0 的段时暴力找到并合并左右两段。太难写了还卡常，遂弃之。

LOJ6777「2021 营员交流」大毒瘤

可以维护火段和非火段，也是特别难写，还有分块做法。反正弃了。

UOJ637【美团杯2021】A. 数据结构

题意

给定序列 a，q 次询问给出 [l,r]，求将 [l,r] 内的数增加 1 后整个序列的数字种类数。n,q\le 10^6,a_i\le n。

题解

首先不存在某数比存在某数好处理，这是因为存在时出现次数不确定，然而不存在就是出现次数为 0，于是用 n-1 减去不存在的个数即为答案。之后考虑拆贡献，即对每个 x 考虑选择哪些区间 [l,r] 会导致不存在 x。

注意到这需要选的区间包含原序列的所有 x，且不能包含 x-1。前一个限制是二维平面上一个矩形，后一个限制是若干不交的矩形，且所有 x 对应的矩形数量总和是 \mathcal O(n) 的。于是枚举后一个限制的矩形并与前一个矩形取交，再进行矩形加单点查即可，扫描线 + 树状数组即可维护，复杂度 \mathcal O((n+q)\log n)。

牛客挑战赛某题

题意

给定三个序列 a,b,c，求所有 l\le r 在三个序列上区间极差的乘积之和。n\le 3\times 10^5。

题解

直接扫，同时维护所有子集区间和即可实现某个序列的区间加，然后单调栈维护一下就行。没题写不了。

lxl 还说，线段树复杂度要分定位和计算两部分，一般来说定位部分比较慢，所以信息多一些对常数的影响不大，只要把信息压结构体里避免重复定位就行。

P11390 [COCI 2024/2025 #1] 教师 / Učiteljica

每个区间内 k 种出现次数的存在性会形成 2^k 种状态，通过容斥转化为求 S 内的次数均不存在的区间数，之后再取补集变成存在至少一个 S 内的次数的区间数，这个就可以直接矩形面积并求了，复杂度 \mathcal O(2^kkn\log n)。当然后半部分也可以不取补集，而是记录 f_i 表示 S 中存在的个数，然后扫描线求全局 0 的数量，复杂度是相同的。之后应该会写。

某典题

题意

给出 n 个区间 [l_i,r_i]，q 次询问编号在 [L,R] 内区间并的大小。n,q\le 10^6。

题解

扫描 R 这一维，维护 f_i 表示当前覆盖 i 位置的区间最大编号，询问 f_i\ge L 的 i 个数（离散化后为权值和）。f 的修改是区间覆盖，于是直接上 ODT，再开一棵线段树 / 树状数组维护每个 L 的答案即可，复杂度 \mathcal O((n+q)\log n)，没题写不了。

10.24 扫描线

多标记问题：

先合并相邻同种标记，尝试交换相邻标记 / 去除无用标记，再考虑标记之间的合并以及信息与标记的合并，以此设计标记。

P3246 [HNOI2016] 序列

题意

给出序列 a，q 次询问区间 [L,R] 内所有子区间 [l,r] 的最小值之和。n,q\le 10^5。

题解

考虑对 R 扫描线，设 f_i 表示当前 [i,R] 的最小值，所求为 [L,R] 区间内 f_i 的历史和。首先 R 移动时可以使用单调栈维护最小值的变化，需要做 \mathcal O(n) 次区间加。之后需要求区间历史和，用任意一种方式维护就行，复杂度 \mathcal O((n+q)\log n)。由于 lxl 刚讲了推标记的方法，写了这个。

P8868 [NOIP2022] 比赛

是上题的双序列版本，lxl 说这种题只需要维护 a,b,ab 的和就能做，之后应该会写。

CF997E Good Subsegments

题意

给出排列 a，q 次询问区间 [L,R] 内有多少个子区间 [l,r] 为区间连续段，连续段定义为其在值域上连续，即 \max-\min =r-l。n,q\le 1.2\times 10^5。

题解

考虑求全局区间连续段数的做法，通过维护 \max-\min-r+l 这个非负值并求最小值 0 的个数求解。同样放到这题，扫描右端点 R，设 f_i 表示 [i,R] 区间的权值，其变化也可以用单调栈表示成 \mathcal O(n) 次区间加。现在要求的是 f 区间历史最值及个数。

使用线段树，设计标记时考虑历史最值累加和加标记的关系，发现不可能出现加标记两侧都是历史标记的情况，否则存在一个历史标记没有用。于是标记为 (l,c,r)，表示先加 l，再累加 c 次历史最值，再加 r。信息就维护当前和历史最值及个数，合并推一推就出来了。总复杂度 \mathcal O((n+q\log n))。听说 CF 题解是分块？怪不得开这么小。

P9990 [Ynoi Easy Round 2023] TEST_90

跟上两题差不多推历史和标记就行，之后应该会写。

P3863 序列

题意

给定长为 n 的序列，q 次操作，区间加或查询某个位置在过去的多少秒内不小于 y。n,q\le 10^5。

题解

由于是区间修改和单点查询历史信息，考虑换维扫描线，扫序列维，维护当前每个时刻对应的值。于是问题转化为在长为 q 的序列上后缀加，求前缀中不小于 y 的个数。使用分块维护，每个块内对所有数排序，修改时给整块打标记，暴力重构散块，复杂度 \mathcal O(\frac qB+B\log B)；查询时整块内二分，散块内暴力查，复杂度 \mathcal O(\frac {q\log B}B+B)，取 B=\sqrt q 可得最优复杂度 \mathcal O(q\sqrt q\log q)。

事实上排序时只有一个后缀加了值，可以分成两半进行归并，这样修改的复杂度就是 \mathcal O(\frac qB+B) 了，平衡平衡可以把 \log q 也放根号里，跑得快了一些。

P7560 [JOISC 2021] フードコート (Day1)

题意

有 n 个队列，每个事件可能向编号在 [l,r] 内的队尾加入 k 个 c，或删掉队头的至多 k 个元素直到删空，过程中询问当前某个队列中第 t 个元素。n,q\le 2.5\times 10^5,k\le 10^9,t\le 10^{15}。

题解

由于每个队列是独立的，修改影响一个区间内的队列，且询问只在单个队列内，考虑换维扫描线，扫描序列维，数据结构维护操作维。这样每个修改只会加入和删除各一次，查询时只考虑操作维的一段前缀即可。

于是操作序列上有一些加入和删除操作，查询进行前缀操作后第 t 个元素。在序列不会删空时是容易做的，只需要线段树二分出所有加入操作的第 (t+s) 小位置即可。可能删空时考虑找到最后一次删空的时刻，从这个位置开始往后做。不难发现这个位置是该前缀内前缀和最小值，于是线段树维护区间和、区间负数的和以及前缀和最小值及位置即可解决，复杂度 \mathcal O(q\log q)。

P11536 [NOISG 2023 Finals] Curtains

题意

给出 m 个区间 [s,e]，q 次询问一个区间 [l,r] 能否被表示为若干给定区间的交。n,m,q\le 5\times 10^5。

题解

选上所有 l\le s\le e\le r 的区间 [s,e] 一定不劣，判断这些区间能否完全覆盖 [l,r] 即可。考虑扫描 r 这一维，对每个点 i 维护 f_i 表示 s\le i\le e\le r 的区间中 s 的最大值。若 [l,r] 内的 f 值均不低于 l，则每个点都能被 [l,r] 内的区间覆盖，否则一定不合法。于是进行区间取最大值，求区间最小值即可，这个可以线段树 \mathcal O((n+q)\log n) 维护。

还有一些别的做法，大概是维护一些奇妙的可合并标记，感觉都没有这种做法好啊，也忘了当时咋做的了，不管了。

10.26 树上问题

P5314 [Ynoi2011] ODT

题意

给定一棵树，需要支持路径加，求一个点及其邻居中第 k 小点权。n,m\le 10^6。

题解

如上述，对每个点用数据结构维护其所有轻儿子的点权，路径修改会影响到 \mathcal O(\log n) 条轻边对应点的数据结构。同时维护每个点的点权，查询时将其父亲和重儿子加入数据结构查询即可，查完再删去，即可做到 \mathcal O(q\log ^2 n) 的复杂度。这个需要卡常，不写了。更低复杂度是极难的，不管了。

不行，太牛了，之后应该会写。

P8511 [Ynoi Easy Round 2021] TEST_68

题意

给定一棵树，点有点权，对每个点求其子树外两点点权异或和的最大值。n\le 5\times 10^5,a_i\le 10^{18}。

题解

性质题。考虑找到全局最大异或和 a_x\oplus a_y，则对于所有 x,y 均在子树外的点 u 均已确定答案，未确定的只有 x,y 两点到根路径上的点。对于这两条路径，其上点子树外的范围从根到底逐渐扩大，可以从根到底依次加入数并实时维护最大异或和。扔到 Trie 树上求一下就好了，时空复杂度 \mathcal O(n\log V)。

P6072 『MdOI R1』Path

题意

给定一棵树，边有边权，选择两条点不相交的路径使得路径边权异或和之和最大。n\le 3\times 10^4,w\le 10^9。

题解

如上，考虑枚举分界点分到子树内外，之后需要分别求子树内外最大路径异或和。首先路径异或和可以用 d_x\oplus d_y 来表示，其中 d_i 为点到根的路径异或和。于是子树外的信息即上题所求，可以 \mathcal O(n\log V) 解决；子树内比较暴力的方式是启发式合并，可以做到 \mathcal O(n\log n\log V)。

考虑进一步优化，再次考虑上题中 d_x\oplus d_y 最大的点对 (x,y)，注意到两条路径外所有点的 f_u 均相同，此时这些点中存在互相包含关系，于是只有极大的子树可能贡献到答案。显然这些子树两两不交，可以直接暴力 \mathcal O(n\log V) 解决。至于路径上的点，从底到根子树依次扩大，按此顺序依次加入即可，总时间复杂度也是 \mathcal O(n\log V) 的。

CF1344E Train Tracks

可以根据树上启发式合并证明限制区间总共只有 \mathcal O(m\log n) 个，通过启发式合并等找出这些区间后贪心即可。之后应该会写。

未公开题目

题意

给定一棵二叉树，每个点上有形如 y\le a 或 y\ge a 的限制，y 值若满足限制则走到左子树，否则走到右子树。要求支持单点修改，查询 y 值从 x 点开始走会停到哪个叶子。

题解

先树剖，之后对于每条重链，用线段树维护 y 要走完某个区间需满足的上下界。走的时候二分一下在当前重链能走到哪，之后跳出去即可，复杂度 \mathcal O(q\log ^2 n)。没题写不了。

神秘来源题目

题意

给定一棵树，每条边有一个字符，询问给出起点 x 和字符串 S，每次走向邻边中在 S 中最靠前的边并将该边删除，求最终停的点。n,q\le 3\times 10^5,\sum=26。

题解

与上题相同，然而这里走一条路径的要求变成若干 i 在 j 前的限制或起来，共 \sum^2 个。这是 01 信息，直接压位存储。然后先向上跳到跳不动，之后再沿着重链跳，跳出重链时可以暴力求下一条重链，复杂度 \mathcal O(q\log ^2n \frac {\sum^2}{w})。lxl 说如果度数太大需要用数据结构维护轻边，不过这题不用。没题写不了。

P8990 [北大集训 2021] 小明的树

把合法转化为灭的灯为连通块，之后点边容斥，扫描线维护。之后应该会写。

10.27 杂题

P6466 分散层叠算法(Fractional Cascading)

题意

给出 k 个长为 n 的有序数组，q 次查询 x 在每个数组中的非严格后继。强制在线，k\le 100,n\le 10^4,q\le 5\times 10^5。

题解

显然有 \mathcal O(qk\log n) 的暴力，即对每个数组分别二分。尝试通过某种方式在第一次二分时处理部分后面的信息。先考虑两个序列的情况，将第二个序列偶数位置的元素插入第一个序列，这样在第一个序列中二分出结果后，第二个序列的答案只会在长为 2 的区间内，可以 \mathcal O(1) 求出。

拓展到 k 个序列的情况，从后往前依次处理，每次将当前序列偶数位置的值插入上一个，使用归并排序即可。这样倒数第二个序列有 1.5n 个元素，之后是 1.75n,1.875n 等等，可以发现永远不会超过 2n。同时预处理出每个序列每个位置及之后第一个当前 / 之后序列元素，这样只需要在第一个序列中二分，后面全都可以 \mathcal O(1) 微调出来，于是可以做到 \mathcal O((n+q)k+q\log n) 的复杂度。

P11721 [清华集训 2014] 玄学

题意

给定长为 n 的原序列 x，要求维护操作序列，支持末尾加入 (l,r,a,b)，表示将 i\in[l,r] 的 x_i\leftarrow ax_i+b；查询给出 L,R,i，求经过编号在 [L,R] 内的操作后 x_i 对 mod 取模的结果。强制在线，模数非质数，n,c\le 10^5,c+q\le 6\times 10^5，c,q 分别为修改和查询数量。

题解

由于多个一次函数可复合成一个一次函数，尝试用数据结构维护经过某段操作区间后的值。考虑离线怎么做，对最终操作序列建线段树，每个点上维护整个序列经过该区间内操作后每个位置的实际变化 A_i,B_i，显然 A,B 只与操作覆盖情况有关。于是 len 个操作的节点会产生的本质不同区间至多 2len+1 个，可以直接维护，父亲节点归并合并两儿子即可，构建复杂度 \mathcal O(c\log c)。查询时在对应节点上分别二分，复杂度 \mathcal O(q\log c\log n)。

至于在线，直接提前开出足够大的线段树，加入新修改时 p 创建右端点为 p 的所有节点即可。复杂度不变，跑得很快，可以通过。还有另一种写法，即二进制分组，维护若干棵大小为 2^t 的树。结尾插入时合并最小的连续若干棵树，形成不完全的线段树结构；查询时在每棵树上分别查，复杂度也是不变的。通过这种写法，以下做法可做到单 log 的复杂度。

考虑若要在同一棵线段树上的某些节点二分，由于父亲节点是子节点归并的结果，可在父亲节点上对两个儿子分别预处理，记录每个元素前面最近的该儿子内元素编号。这样可以只在根节点上二分一次，之后 \mathcal O(1) 查表即可得到每个点上的二分结果。该技巧称为“归并树”。

现在还需要对 \mathcal O(\log c) 个根节点二分，考虑分散层叠，即对于目前存在的所有树 p_k，令其按大小 s_{p_i} 从大到小排序。之后从前往后依次从 w_{p_i} 中等分取出 s_{p_{i+1}} 个元素归并进 w_{p_{i+1}}，这样序列长度翻倍，只会贡献常数。同时每次插入时会找前面某个根插入若干元素到该根，然而每个根 u 只会向后贡献 \mathcal O(\frac {s_u}{2^t}) 个元素各一次，总共就是 \mathcal O(s_u) 次，于是构建复杂度还是 \mathcal O(c\log c)。

查询时直接二分出 p_k 的答案，然后可将 p_{k-1} 的答案缩小到长为 \mathcal O(\frac{s_{p_{k-1}}}{s_{p_k}}) 的区间内，只对该区间二分即可，以此类推。总复杂度为 \mathcal O(\log s_{p_k}+\sum_{i=1}^{k-1}\log {\frac{s_{p_i}}{s_{p_{i+1}}}})=\mathcal O(\log s_{p_1})=\mathcal O(\log n)，于是查询复杂度为 \mathcal O(q(\log c+\log n))，然而由于常数大，实际上比两个 log 做法跑得慢。

10.28 做题？

问题

关心组合结构：整体结构 / 个别判定。

组合研究工具：调整 / 差分生成 / 整体刻画观察。

研究方法

特例、特殊性质 / 画图、打表、渐进估计、验证。

可能性质 / 信息压缩、化简 / 刻画形式。

问题分类

UOJ792【UR #24】比特跳舞

讲“做题？”的例题，考虑刻画奇数个本质不同子序列的限制，发现可以从开头起每次跳到下一个相同位置，看是否能跳完即可。然后再注意一下或打表可以发现树上形成了若干个组，每个组内两两合法。于是用每对极小合法对合成大的组即可。之后应该会写。