我要加训数据结构/ll/ll

· · 个人记录

前面忘了，总之省集前补点基本功。

别光做 \text{polylog}，记得最后再写点根号题。

题目全部来自于之前集训的课件。

AT_iroha2019_day4_l ...好きです

因为查询的是 \max，所以可以放心地通过分讨去掉答案式子的绝对值，然后发现相当于查询 (x,0) 到一个点集内的点连线的斜率最值。

经典的结论是，答案只会在凸壳上的点取到，所以我们只需要知道当前时刻的凸壳即可查询答案。

有加点和删点操作，容易想到线段树分治，这里线段树上的点是出现时间包含当前区间的点，把凸壳预处理出来后线段树所有访问过的凸壳都要查询一次。

需要注意的是，先给所有点按照横坐标排序再插入，这样求凸壳的时候可以省去排序，同时查询的时候也有单调性，不然会多 \log，最后是 O(q\log q) 的。

代码。

YDRG005D 使一颗心免于哀伤

先考虑这么一个问题：区间插入删除直线，区间查询某 个点 x 处的点值 \max 该怎么做。

可以注意到，如果查询的区间内重复出现了多次某条直线是没有用的。换句话说，假如在区间 [l,r] 插入，它对询问区间 [ql,qr] 只要交集不为空就能产生贡献。

这个限制可以这样解决：开两棵线段树，修改的时候第一棵线段树在 \log 个完全包含的区间插入，第二棵线段树在所有经过的区间插入；查询的时候，第一棵线段树在所有经过的区间更新答案，第二棵线段树在 \log 个完全包含的区间更新答案。分讨所有修改和查询区间之间的关系，可以证明这么做的正确性。

插入的时候具体怎么做也是在线段树上维护凸壳，和上一题差不多。

现在还给查询的集合加入了时间的限制，其实是一个道理，只要出现的时间再有交即可，可以再用上面的方式分两种情况处理，也就是直接跑四遍线段树分治。

时间复杂度是 O(n\log^2 n) 的，四倍常数，代码没写。

UOJ462 新年的小黄鸭

直接设 dp_u 表示只考虑 u 子树内时的最小代价。

考虑一个暴力，枚举 u 子树内的一个叶子 v，尝试将 u 到 v 的整个路径划为一条链，首先挂出去的子树都先有一个 dp+siz 的贡献，然后再加上 u 到 v 的链长取 \log 即可。

优化是简单的，直接把叶子按照 dfs 序排序后建线段树，直接维护每个叶子转移过来的代价是容易的，直接做就是 O(n\log^2 n) 的，代码。

下面是云浅的做法。

我们设 dp_{u,x} 表示考虑 u 的子树且 u 上方挂了 x 条重边的最小代价，同时延迟计算重链长度的贡献。枚举儿子 v 是重儿子，那么 dp_{v,x+1} 会转移到 dp_{v,x}，其它儿子 v' 的贡献就是 dp_{v',0} 加上 \log x。注意到加 \log x 可以先拆成 \log 次区间加，剩下的就相当于是对位 chkmin（可能要把下标平移下，因为是 dp_{v,x+1} 转移到 dp_{u,x}，比如第二维换成 dep_u-x）。

直接线段树优化显然时间上可以做到 O(n\log^2 n)，但是空间复杂度比较难说，而且这个线段树合并还要下放标记，常数巨大。

有这么一个技巧，先 dfs 重儿子，儿子的线段树合并过来后立马销毁，这样祖先上至多有 \log 棵线段树，即使每棵线段树是满的空间复杂度也才 O(n\log n)，这个分析还比较松，所以很没问题！但是我没写代码。

云浅说正常情况线段树合并这么做空间是线性的。

QOJ3998 The Profiteer

前面忘了，正睿搬过。

P4234 最小差值生成树

不会 LCT 该怎么办呢？自己编了个和上题一样的分治做法。

设 f_l 表示最小的 r\ge l 使得保留图中边权在 [l,r] 内的边图连通，显然答案是最小的 f_l-l。

注意到 f_l 具有单调性，考虑决策单调性分治。记 \text{Solve}(l,r,s,t) 表示已经确定了 f_l,f_{l+1},\ldots,f_r 的取值在 [s,t] 内。

取 mid=\lfloor\frac{l+r}{2}\rfloor，考虑从 mid 开始从小到大加入各种边权的边，找到第一条加入后连通的边，则 f_{mid} 的值就是它的边权 w。根据单调性，可以直接递归到子问题 \text{Solve}(l,mid-1,s,w) 和 \text{Solve}(mid+1,r,w,t)。

注意这种分治为了保证复杂度，我们需要确保每一层递归枚举到的边数总和是线性的，解决方法是直接要求边权大小在 (r,s) 内的边递归前已经加入并查集内即可。

复杂度是两个 \log，抢到了最优解，代码。

P5314 [Ynoi2011] ODT

路径修改邻域查询，考虑对每个点的轻儿子开一个数据结构，因为树剖后一次路径加只会影响 \log 条轻边，所以也只有 \log 个点的数据结构需要修改。

对于本题就是每个点开一棵平衡树插入所有轻儿子的点权，路径加只需要改 \log 个平衡树。查询的时候，只需要把重儿子，自己和父亲的点权插入到平衡树里再查询即可，复杂度是 O(n\log ^2 n)。当然这里显然修改数比查询数多，可以平衡一下除以个 \log\log n，但是没有必要。

总之是个很有启发性的题，或许邻域查询的题目都可以这么考虑。

代码，偷懒用了 pbds 竟然能过。

QOJ5020 举办乘凉州喵，举办乘凉州谢谢喵

现在我感觉我对树剖的理解深刻了一些！/fendou

先考虑询问的路径 x,y 是一条祖先后代链的情况，这里认为 y 是 x 的祖先。首先 y 子树外的点可以直接点分治处理掉，所以只需要考虑 y 子树内的点如何统计。

直接先上树剖，这样路径上只会有 \log 条轻边。延续上一题的思想，可以考虑求出每个点所有轻儿子子树对应的信息，这样可以直接简单地累加，只有 \log 个轻儿子在路径上的点需要特殊处理。具体地，设 f_{u,d} 表示 u 子树内和 u 的距离 \le d 的点的个数，g_{u,d} 表示 u 所有轻儿子的子树内和 u 的距离 \le d 的点的个数，路径上的轻边是 (u_1,v_1),(u_2,v_2),\ldots,(u_k,v_k)（u_i 是 v_i 的父亲），询问的答案就是路径上的点数，加上每个点的 g_{u,d}，减去所有的 f_{v_i,d-1}，加上所有的 f_{son_{u_i},d-1}（son_u 表示 u 的重儿子）。

将询问差分一下，问题形如 O(n\log n) 次查询某个 f_{u,d}，O(n) 次查询一个点到根的路径上的 g_{u,d} 之和。对于 f 的查询，这个比较简单，直接 dsu on tree+BIT 统计即可。对于 g 的查询，我们首先要明白一点就是树上所有轻子树的大小之和只有 O(n\log n)，这允许我们直接暴力。维护一个数据结构 G，G_i 存储当前点到根路径上所有 g_{u,i} 之和，遍历到一个点 u 直接枚举轻儿子子树内的点插入即可，可以树状数组维护。

最后解决一个问题：查询的路径不是祖先后代链咋办。设 z=\text{LCA}(x,y)，我们可以直接将查询平凡地拆成 x 到 z 的答案与 y 到 z 的答案拼起来，发现多算的部分只有 f_{z,d}，所以完全一致。

这样做是 O(n\log^2 n) 的，似乎简单优化后可以做到 O(n\log n)，但是我暂时懒得想，而且两个 \log 跑得飞快啊！代码。

P5311 [Ynoi2011] 成都七中

考虑固定住根 x 怎么做。容易发现，对于一个点 u 来说，设 u 到 x 路径上的编号最小值和最大值分别为 x,y，那么当 [x,y]\in[l,r] 的时候 u 会和 x 连通。现在要做的就是在和 x 连通的 u 中再数颜色，这是容易的，直接扫描线即可解决。

这种和根的连通性相关的题继续优化一般是考虑点分治。设当前的分治中心为 rt，可以发现的一个性质就是，假如点 u 上有一个询问 (l,r,x) 且 u 到 rt 上的最小值和最大值都在 [l,r] 内，那么这次询问来说 u 和 rt 其实是连通的，所以这个询问等价于在 rt 上进行 (l,r,x) 的询问。直接遍历当前的连通块，把和 rt 连通的询问做掉，不和 rt 连通的询问显然可以递归到子问题解决。

时间复杂度 O(n\log^2 n)，应该也可以平衡下除以个 \log\log n，代码。

QOJ8547 Whose Land?

首先 k 邻域可以拆成 bfs 序的 O(k) 个区间，具体怎么拆大概可以在每种深度二分出来。

然后直接扫描线扫 r，每次把一个点的 O(k) 个 bfs 序区间加入。对每个位置 x 维护 mx_x 表示最大的 i 使得 x 在 i 的 k 邻域内，每次加入区间显然就是对 mx 做若干次区间覆盖，而查询的答案就是 \sum_{i=1}^n[mx_i\ge l]，显然可以 ODT+BIT 简单维护，复杂度 O(nk\log n)，代码。

P7952 [✗✓OI R1] 天动万象

非常有意思的题。

先思考一条链的情况该怎么做，每次修改操作会选择一个后缀，然后将点权整体向前平移，再删去最后一个点，这个过程可以简单地用平衡树维护。

你发现每次操作后会删点，说明这背后可能就有个均摊在。放到树上，可以发现一次操作会删掉子树内的所有叶子，那如果我们一次操作的复杂度和删去的叶子数相关就行了。

考虑给树瞎几把做个链剖分，那么当前树链的个数就等于叶子的个数。考虑给每条链开一棵平衡树，一次修改直接把子树内的每条链挨个平移（还有链顶给父亲做单点加）。考虑如何查询，首先 u 自己的链会查一个后缀 \max，考虑直接把每条链的 \max 挂在链顶上，子树内其它链的贡献只需要查个子树 \max，可以线段树维护。

可能有比较多的细节，有时候会删出一条链的链底不是叶子的情况，这时候它肯定恰好有一个儿子，需要把它和儿子的链合并一下，不然复杂度会错。

代码就懒得写了。

P7124 [Ynoi2008] stcm

有点深刻。

众所周知子树在 dfs 序上是区间，但是这些区间之间其实还有个更强的性质：要么不交要么包含。考虑直接分治，设 \text{Solve}(l,r) 表示当前已经加入了 dfs 序上 [l,r] 以外的点，要处理跨过 mid 的子树。由于前面的性质，跨过 mid 的区间两个端点都是单调的，所以一层的询问可以直接线性次操作做掉。

显然次数是 O(n\log n) 的，代码。

QOJ8006 Dinosaur Bones Digging

一个容易想到的想法是对值域从大到小扫描线，找到当前的最优区间。加入一个数会给包含它的区间 +1，放在平面上相当于是散点集矩形加查全局 \max，这个东西直接做可能只能 KDT 到根号，不太懂，反正不能 \text{polylog}。

那背后肯定是有更强的性质在的，考虑一个区间如果被另一个区间包含，那么这个区间肯定是不优的，所以这种区间可以直接删掉。现在只剩下一些不会有包含关系的区间，经典性质就是它们按照左端点排序后右端点也有序，那么一次加点就会变成区间加，然后就能做了。

思想就是通过调整出一个更简单的结构来方便维护，感觉启发性还是很强的。

复杂度显然是 O(n\log n) 的，代码。

QOJ964 Excluded Min

首先考虑一个确定集合 S 的 F(S) 如何计算，答案是最大的 x 使得 \sum_{y\in S}[y<x]\ge x。

然后思路很自然又会变成从大到小加数，再次变成矩形散点加查全局 \max。但是这里我们需要对每个区间都回答，不能把一个区间简单地删去，该怎么办呢？

包含关系的区间仍然是有性质的，具体来说如果 A\subseteq B，那么显然 F(A)\le F(B)。尝试利用这一点，初始时我们仍然只保留不被包含的区间，扫描线的过程中如果有区间已经找到了答案就把它删去，然后此时会产生一些新的不被包含的区间，把它们加入即可。

具体实现比较繁琐，需要用到若干数据结构维护上面的过程，复杂度还是 O(n\log n) 的，代码待补。

P9337 [Ynoi2001] 冷たい部屋、一人

考虑 y_i=i 的时候就是相等 pair 个数，所以有矩阵乘法规约，直接想根号做法就可以了。

先对出现次数根号分治。对于次数 \le B 的数字，考虑直接枚举一对，求出区间 \min 和 \max 之后变成 O(nB) 次修改和 O(n) 次查询的二维数点，上个分块平衡一下是单根号的。

对于次数大于 B 的数字，每种数字分开做。考虑两个相邻的出现位置，把它们中间的数缩掉，只保留 \min 和 \max，得到一个长度为 O(cnt) 的序列。把查询端点离散化掉，然后对值域跑个回滚莫队，相当于会在序列中激活一个位置然后要维护被激活的连续段，直接做就可以了。但是需要实现得相当精细，不能让离散化带 \log。

反正总共就是一个根号，代码懒得写了。

CF2043G Problem with Queries

显然问题与区间相等 pair 数等难，直接想根号，还带强制在线当然是直接考虑分块了，虽然好像莫队其实有方法在线的来着。

首先散块对散块，散块对整块的贡献都是好维护的，只需要考虑整块对整块之间的贡献如何算。设 cnt_{i,j} 表示前 i 个块数字 j 出现了几次，假如询问时需要考虑第 l 块到第 r 块，我们不妨直接计算 \sum_{x}(cnt_{r,x}-cnt_{l-1,x})^2，这个的结果减去区间长度再除以 2 就是真正的答案。

将平方拆开变成 \sum_x(cnt_{r,x}^2-2cnt_{r,x}cnt_{l-1,x}+cnt_{l-1,x}^2)，第一项和最后一项两个平方和显然是好维护的，考虑中间那一项。直接定义 w(l,r)=\sum_x cnt_{l,x}cnt_{r,x}，考虑一次修改对 w 产生的影响，把 w 看成一个矩形的话，修改相当于总共做 O(\frac{n^2}{B}) 次横线加或竖线加，而我们需要查 O(n) 次单点和。

因为修改操作很多所以通过差分把修改变成单点修，对矩形 w 的每行每列开一个差分数组维护修改的增量。注意到 w 的大小是 \frac{n}{B}\times\frac{n}{B} 的，所以查询一个位置的时候可以暴力遍历它所在行列的差分数组，取 B=\sqrt n 复杂度就是正确的。

综上本题做到了 O(n\sqrt n)。

P9040 [PA 2021] Desant 2

序列给定时，设 f_{i} 表示前 i 个位置的答案，显然 f_{i}=\max({f_{i-1}},f_{i-k}+\sum_{j=k+1}^ia_j)，第二种转移可以前缀和，然后发现这个 dp 好像只能优化到一次线性。

能转移到 i 的位置非常简单，所以考虑把 dp 转移的 DAG 画出来，相当于是每个点 i 会向 i+1 连一条零权边，向 i+k 连一条边权为 \sum_{j=i+1}^{i+k}a_j 的边，然后每次询问相当于查询两点直接的最长路。继续发掘图的性质，把图画的方正一点，让点 i 变成点 (\lfloor\frac{i}{k}\rfloor,i\bmod k)，会发现这张图几乎就是一个网格图，唯一的问题是最后一列会向第一列连一些额外的边。

假如图就是网格图，可以直接分治，每次选边长长的一侧折半，枚举经过中线上的一点处理所有询问，这里因为是 DAG 每层跑一次单源最短路是 O(n) 的，且中线长度显然不超过 O(\sqrt n)，所以复杂度是 T(n)=O(n\sqrt n)+2T(n/2)=O(n\sqrt n) 的。

对于本题最后一列向第一列额外多的边，直接在第一次分治的时候把额外边的端点也枚举上再跑最短路即可，这种情况只会发生在某一次分治所以不影响复杂度，仍然为 O(n\sqrt n)，代码。

P5064 [Ynoi Easy Round 2014] 等这场战争结束之后

遇到这种回退版本不会直接处理的时候记得考虑建操作树。

直接在 dfs 版本树的时候维护答案，我们需要一个不依赖于均摊的可撤销数据结构。首先只查询排名可以把值离散化成排列，然后考虑对值域分块，维护 f_{i,j} 表示第 i 个连通块有多少个在第 j 个块内的数字，合并和撤销的复杂度都是块的个数。

查询的时候只需要找到在哪个块内，然后暴力扫散块即可，需要一些手段卡下空间。