DS 小练（1）

此篇总结部分为这篇博客和这篇博客的注解，在这里向整理这些题目的作者表示感谢。

---

[2] [ROI 2021] 砍树 (Day 2)

有点困难。难以模拟过程，把每个点的贡献摊出来，如果找出 $L_i,R_i$ 表示区间左端点 $\le L_i$ 时 $i$ 才能向左砍 / 右端点 $\ge R_i$ 时 $i$ 才能向右砍，那么最后贡献是好算的，数点容斥一下就好，问题在于怎么算 $L,R$，以 $L$ 举例。

因为 $\forall L_i\le j\le i,L_i\le L_j$，也就是 $L$ 有包含关系，所以做一个类似整体二分的东西，不一样的点在于我们将集合分成 $\le mid$ 和 $> mid$ 的部分，而判定可以直接先加入 $mid$，再按顺序加入当前集合的树，能往左就往左，用栈维护，手模一下发现不在当前集合的点不加到栈里不会对求 $L$ 造成影响，因为 $L$ 是包含关系。

[2] QOJ964 Excluded Min

容易发现答案为 $\max\limits_{v}v[\sum\limits_{i\le v}a_i>v]$。对值域从大往小扫描线，区间很难更新。但是如果所有询问区间两个端点分别单调，那就是好做的。对于询问 $[l,r],[l',r']$，如果有 $l\le l'\le r'\le r$，前者的答案肯定比后者大。开始先加入极大的互不包含的区间，每次一个区间更新到了答案，就把其所有包含的区间加入。具体的，如果删除了 $[l,r]$，令其原来的后继区间左端点为 $l_n$，前驱的右端点为 $r_p$，每次找到左端点在 $[l,l_n)$ 且右端点最大的区间 $[l',r']$，如果 $r_p < r'$，那么更新 $r_p=r'$，继续递归找，否则停止找，$\mathcal O(n\log n)$。

[0] [USACO23FEB] Hungry Cow P

可以线段树分治 + 可持久化线段树。遇到这种单向关系（如这题就是草只会影响后面的天），试着用单侧递归线段树，具体每个区间维护有草天数，溢出草数以及答案。如果某些题要维护 $\max,\min$ 等信息需要额外维护对应某个儿子的信息。

[1] 「JOISC 2019 Day3」穿越时空 Bitaro

我们希望维护一个分段函数，这题神奇的一点是整个关系可以通过两种类型表示：如果两个区间 $[l,r],[l',r']$ 合并：

• 两者如果有交，等价于通过 $[l,r]\cap [l',r']$。
• 如果无交，令 $r<l'$，等价于钦定必须从 $r$ 时刻进去，$l’$ 时刻出来。

再分讨一下必须从 $x$ 时刻进去，$y$ 时刻出来和区间 $[l,r]$ 的合并关系：

• 如果 $y\in [l,r]$，等价于 $x$ 时刻进去，$y$ 时刻出来。
• 如果 $y<l$，等价于从 $x$ 时刻进去，$l$ 时刻出来，$r<y$ 类似。

于是直接线段树维护。

[0] [COTS 2017] 盗道 Krimošten

因为没有修改，所以直接维护分段函数，$\mathcal O(n\log^2n)$。如果查询都是 $[1,n]$，可以直接用线段树维护值域。比较好的一点如果初始值域为 $[-V,V]$，那么 $n$ 次操作后的值域一定至少为 $[-V+n,V-n]$，且连续。于是每个询问在 $l$ 处找到和 $c$ 相等的一个位置，同时在 $r$ 再次查询即可。

[1] [集训队互测 2018] 完美的队列

考虑根号。算出每个询问什么时候被彻底弹出，剩下是二维数点。对序列分块，整块弹出时间可以对每块双指针；散块拆成点，可以树状数组二分，$\mathcal O(n\sqrt{n\log n})$，这个其实也可以根号平衡，具体记录每个值在序列中的块编号，严格根号。

---

polylog 做法。类似分块，把询问放到线段树上。线段树上每个点只和其祖先 / 子树上挂的修改有关，其中子树修改量总和是 $\mathcal O(n\log n)$ 级别的；又因为所有祖先修改都是整体修改，可以直接在线段树上 dfs，继承父亲的操作。具体的，维护一个线段树，记录每个时间整体加的值，统计一个点的时候把所有子树修改提取出来，子树修改之间的全局修改可以线段树上查询，$\mathcal O(n\log^2n)$。

[2] JOISC 2020 掃除

先考虑 sub3 怎么做。因为推了一次之后肯定还是满足两维单调的性质，线段树就可以维护。如果初始不满足这条性质，画画图发现，对于至少被扫帚扫过一次的点集合一定也是单调的，预处理出所有点被第一次扫到的时间，再用平衡树维护点集。最后插入点操作是简单的，因为我们批量处理是容易的，所以把每个修改区间放到线段树上。具体的，令 $\{Q_u\}$ 表示 $u$ 被询问的时间，那么把 $(Q_{i-1},Q_i]$ 放到线段树上，再对树 dfs 一遍，每个点都做一遍 sub4，$\mathcal O(Q\log ^2 Q)$。

[0] [THUPC 2023 决赛] 先人类的人类选别

从冒泡排序等角度来看比较复杂，先差分，对于每个前缀 $a_{1\sim m}$，插入了 $k$ 个数之后的前缀和 $s_m$ 为 $a_{1\sim m}$ 和插入 $k$ 个数的前 $m$ 大之和，主席树随便维护。

[2] 【MX-S8-T4】平衡三元组

条件转成 $2y\le x+z$，那么 $x,z$ 之一必然取到最大值，令 $x$ 为最大值，位置为 $p_0$。生成序列 $\{p\}$，其中 $p_i$ 是 $(p_{i-1},r]$ 的最大值位置。容易发现答案只会在 $x=p_0,y=p_{i-1}/\max\limits_{j=p_{i-1}+1}^{p_i-1}a_i,z=p_i$ 取到，第一种限制了 $\{p\}$ 长不超过 $\log V$，复杂度 $\mathcal O(n\log n\log V)$。

[2] [GDKOI2023 提高组] 树

**遇到无修改，与二进制有关的结构，可以联想到倍增。**但是这题子树内并不好处理，我们给每个点标一个 dfn 序，令 $S_u$ 为所有 $v$ 满足 $d_v\ge d_u$，且 $dfn_v\le mx$ 构成的集合，其中 $mx$ 是 $u$ 子树中最大的 dfn。如果 $f_{u,i}$ 表示 $S_u$ 中所有深度 $<d_u+2^i$ 的节点答案，此时就可以倍增了，后面是容易的。询问在线，$\mathcal O(n\log n)$。

---

遇到与深度有关的问题，可以联想到长剖。令 $f_{u,i,j}$ 表示计算所有 $u$ 的子树中，深度在 $[d_u+i,d_u+i+2^j)$ 的点构成集合的答案（这里深度基准是 $d_u+i$）。处理点 $u$ 时，$f_{u,>0,*}$ 的值可以直接暴力合并得出，而 $f_{u,0,*}$ 可以倍增计算。但是此时要快速求出一个深度区间内点的信息，然而长剖并不支持前缀和。观察到每次修改的只会是一个前缀，那么可以维护后缀和。询问离线，$\mathcal O(n\log n)$。

[0] 「LAOI-16」天外来物

初始切入点应该是求出所有本质区间，但是这个量级是 $\mathcal O(n^2)$ 的，说明我们肯定要对这个玩意儿扫描线。发现如果 $[l,r]$ 是本质区间，那么 $l,r$ 端点均应该是 $[l,r]$ 构成虚树的叶子，也就是对于 $l/r$，另外 $r-l$ 个节点一定在其一棵子树内，否则这个点不是叶子。可以记录一个双向限制的单调信息：令 $p_i$ 表示最大的 $p_i=j$ 使得 $[i,j]$ 构成的虚树中 $i$ 是叶子，同理容易求出 $s_i$，那么等价于求 $[l,r]$ 的个数，满足 $L\le l\le r\le R$，且 $s_r\le l,r\le p_l$。对 $r$ 扫描线。维护序列 $a,b$，每次操作为对于所有 $a\leftarrow a+b$，单点修改 $b$，这是容易 1log 的。

[3] [JOIST 2022] 鱼 2

如果没有修改怎么做。从单点贡献入手，一条鱼有自己的管辖区间 $[l,r]$，且只有在询问区间 $[L,R]\subseteq [l,r]$ 的时候会产生贡献。求每条鱼的区间可以每次贪心两边拓展，易证这部分是 $\mathcal O(n\log n\log V)$ 的，剩下的就是个二维数点。

带上修改，很大一部分题逃不过线段树或者根号算法，我们尝试维护每个区间的答案和一些必要的信息。对于一个线段树上的区间 $[L,R]$，如果一条鱼的区间 $[l,r]\subseteq(L,R)$，在之后的合并过程中肯定不会被统计到答案里。所以只要记录区间经过 $L/R$ 的鱼的信息。而且分析一下可以得出，经过一个固定点的管辖区间个数不超过 $\mathcal O(\log V)$ 个，那么每个节点直接维护经过 $L/R$ 的管辖区间，以及其对应的鱼的条数。合并的时候做一个双指针状物，复杂度 $\mathcal O(n\log n\log V)$。

[1] QOJ967 Rectangle Painting

如果不强制在线，倒着做，每次对区间 chkmin。发现维护所有不再集合中数的 min 是比较容易的。对于每个值维护一个 ODT，存所有没有这个值的连续段。把每个连续段摊到线段树上，一个节点的 mex 就是这个节点所有祖先集合的最小值再取 min，容易维护。

[0] QOJ9708 Yuuki and a problem

没写。单修区间查询信息可以 bit 套线段树，还是好写的，3log。或者可以直接线段树，每个节点维护在跳的过程中的断点，合并的时候双指针，容易发现是 2log 的，更好写的方法是直接记录 $mn_i,s_i$ 表示所有 $i=\lfloor\log x\rfloor$ 的 $x$ 最小值和。查询的时候从 $1$ 开始跳，因为如果包含了任意一个在 $[2^k,2^{k+1})$ 的元素，下一步一定跳出这个区间了，同样也是 2log。

[3] 【MX-S10-T4】『FeOI-4』呼吸之野

对于一个查询，把 $a_i\ge x$ 标为 $1$，$a_i<x$ 标为 $1$，好区间的条件为区间和 $\ge 0$ 且长度 $\ge k$。对 $x$ 从小到大扫描线，同时维护 $f_i$ 表示以 $i$ 为右端点的合法区间中，最小的左端点，发现如果存在一个时刻 $[i,f_i]\subseteq[j,f_j]$，那么 $j$ 之后就没用了，每次扫描的时候删去所有无用的 $f_j$，剩下来的 $i,f_i$ 均是单调的，询问就可以直接二分出来。

但是动态更新 $f_i$ 不太好做，观察到一个右端点 $j$，在扫描 $x$ 的过程中存活的一定是一个前缀，于是我们可以用一个 $t_i$ 刻画一个右端点的存在时间。考虑对下标扫描线，假设当前在处理下标 $i$，二分存活时间 $t_i=x$。令上一个在 $x$ 时刻存活的区间为 $[l_x,r_x]$，如果 $\sum\limits_{j=r_x+1}^{i}a_j> 0$，那么必有 $l_x<f_i$，$f_i$ 不会被支配；否则有 $r_x-k+1< f_i$，因为要是 $f_i\in(l_x,r_x-k)$，那么 $[r_x-k+1,r_x]$ 也合法。整理一下有 $f_i\in(r_x-k+1,i-k+1]$，判定条件变成了这个区间内有没有一个下标 $f_i$ 满足 $sum_{f_i-1}\le sum_i$。动态对于每个 $x$ 维护此时的 $\sum\limits_{j=r_x+1}^ja_j$ 和 $sum_i-\min\limits_{j=r_x-k+1}^{i-k}sum_j$。求出 $t_i$ 容易在线段树上二分，具体的，每个线段树节点维护区间最后一个数对应的信息，二分的时候可以直接通过左儿子的信息判断递归哪一侧，这样可以避免整体信息合并。修改就把线段树上 $[1,t_i]$ 的 $r_x$ 变成 $i$，信息也对应修改，这部分是 $\mathcal O(n\log n)$ 的。

但此时有个问题，我们回答询问的时候只知道剩余的右端点，单次求一个 $i$ 对应的 $f_i$ 是 $\mathcal O(\log n)$ 的，再加上二分是 $\mathcal O(\log^2n)$ 的。将上面过程反过来，求出所有合法的左端点时间，那么一个时刻存在的左右端点一定是顺序匹配的，单独二分，复杂度 $\mathcal O(n\log n)$。

[1] PKUSC2021 逛街

如果只考虑询问，单侧递归复杂度是 $\mathcal O(\log^2n)$ 的，肯定不行，如果从单点贡献考虑，那是个动态二维数点。所以我们直接模拟询问：每次找到下一个比当前大的值，这个值是确定的。可以根据这个关系建立一棵树，因为值之间的相对关系不会变化，所以询问只要做一个到根的链查。修改需要维护每个值的连续段大小，如果一个段前面的值比这个段的值小，那么操作一轮长度就会 $+1$；同理，如果后面比这里大，每操作一轮就会 $-1$。直接线段树维护每个段的值，还有节点子树中最小的段长，容易 $\mathcal O(\log n)$ 维护，$\mathcal O(n\log n)$。

[NOIP2022] 比赛

[CEOI 2025] Equal Mex

[] QOJ4914 Slight Hope

QOJ3576 Zhylan.io

P8861 线段

[HNOI2010] 城市建设

「CGOI-3」灵气

QOJ12001 Cookies

QOJ12012 Yosupo’s Algorithm

「雅礼集训 2017 Day7」事情的相似度

[CTS2022] 普罗霍洛夫卡

[CTS2022] 燃烧的呐球

【UNR #5】诡异操作

【ULR #2】Picks loves segment tree IX