数据结构题泛做 2024-04-10 08:22 folder 学术

1. 「CodeChef WALKBT」Walks on the binary tree
2. 「Codeforces 464E」The Classic Problem
3. 「洛谷 P8860」动态图连通性
4. 「洛谷 P8861」线段
5. 「Codeforces 1408H」Rainbow Triples
6. 「Codeforces 1515I」Phoenix and Diamonds
7. 「IZhO 2022」Zhylan.io
8. 「2019 ICPC Asia Xuzhou Regional」Yuuki and a problem
9. 「Ynoi2003」博丽灵梦
10. 「Ynoi2079」riapq
11. 「Ynoi2004」rsxc
12. 「Ynoi2005」rmscne
13. 「IOI2021」分糖果
14. 「HNOI2010」城市建设
15. 「Codeforces 603E」Pastoral Oddities
16. 「AHOI2013」连通图
17. 「NOIP2022」比赛
18. 「Ynoi2008」rdCcot
19. 「CF1548E」Gregor and the Two Painters
20. 「2022 ICPC Asia Jinan Regional」Tree Distance / 「Ynoi2004」rpmtdq
21. 「北大集训 2021」小明的树
22. 「PKUSC2021」逛街
23. 「BalticOI 2021 Day1」Inside Information
    1. I
    2. II
24. 「洛谷 8959」「CGOI-3」灵气
    1. I
    2. II
25. 「XX Open Cup, Grand Prix of Tokyo」Cookies
    1. I
    2. II
26. 「XX Open Cup, Grand Prix of Tokyo」Yosupo's Algorithm
27. 「Ynoi2009」rprmq1
28. 「Ynoi Easy Round 2022」超人机械
29. 「Ynoi Easy Round 2022」虚空处刑
30. 「Ynoi2002」Goedel Machine
31. 「Ynoi2011」成都七中
    1. I
    2. II
32. 「Ynoi2006」rldcot
    1. I
    2. II
33. 「雅礼集训 2017 Day7」事情的相似度
34. 「洛谷 6292」区间本质不同子串个数
35. 「洛谷 7361」「JZOI-1」拜神
36. 「UR #20」机器蚤分组
37. 「Ynoi2005」vti
38. 「Ynoi2003」铃原露露
39. 「CTS2022」普罗霍洛夫卡
40. 「Ynoi2005」rpxleqxq
41. 「Ynoi2002」Optimal Ordered Problem Solver
42. 「Ynoi2008」stcm
43. 「Ynoi2007」rfplca
44. 「Ynoi2006」spxmcq
45. 「Ynoi2008」rplexq
46. 「Ynoi2002」Adaptive Hsearch&Lsearch
47. 「CTS2022」燃烧的呐球
48. 「Ynoi2009」rprmq1
49. 「XXI Open Cup, Grand Prix of Nizhny Novgorod」Rectangle Painting
50. 「Ynoi2003」赫露艾斯塔
51. 「JOISC 2019 Day2」两个天线
52. 「IOI2018」排座位
53. 「Ynoi Easy Round 2022」堕天作战
54. 「UNR #5」诡异操作
55. 「ULR #2」Picks loves segment tree IX
56. 「UNR #7」鸽子收费站

「CodeChef WALKBT」Walks on the binary tree

考虑经典的虚树大小求法。不赘述。
那么关键矛盾在于如何快速比较两个 X 的字典序大小并求 LCP。
发现可以用主席树维护。进位是一段区间覆盖和至多一次单点修改。
O(nlog2n)。

「Codeforces 464E」The Classic Problem

Dijkstra，用主席树维护 dis，维护方式见上题。

「洛谷 P8860」动态图连通性

我们只需要找一条路径使得在询问中出现最晚。
考虑设倒着的时间戳为 t，设边权为 2t，然后就是上一题。

「洛谷 P8861」线段

有个部分分提示分治。不难想到分治就是解决了相交的问题，因为我们钦定了交点。
我们把区间 [l,r] 放在分治区间 [L,R] 中，使得 L≤l≤M<r≤R，其中 M=⌊L+R2⌋。
对于修改和询问，只需将区间挂到对应的结点上（相交且不包含），根据线段树这是 O(logmaxri) 个点。
修改就是左端点 max，右端点 min，且我们分治后只需要分别维护 l 和 r 的集合，而不必考虑其配对。用线段树或树状数组即可。查询类似。

「Codeforces 1408H」Rainbow Triples

记 lim=⌊#02⌋，显然每个非 0 的数至少会有一边有 ≥lim 个 0。
两边都 ≥lim 的可以先处理掉。设左边 ≥lim 的为 SR，右边 ≥lim 的为 SL。
考虑每种颜色只需要保留 SL 中的最右点和 SR 中的最左点。
接下来我们考虑这是一个类似匹配的过程，不妨建出最大流图：S 连向每个颜色，每个颜色连向至多两个位置，SL 中的位置连向左侧的位置，SR 中的连向右侧，0 连向 T。
然后考虑计算最小割，显然只会割和 S,T 相连的边，且是 SL 的一个前缀，SR 的一个后缀，和中间的一些颜色边。
枚举一边，用数据结构维护另外两边即可。

「Codeforces 1515I」Phoenix and Diamonds

倍增分块。考虑 c∈[2k,2k+1)。
我们先来考虑是否能取一个 ≥2k 的数，那我们知道如果取了，其前方所有 <2k 的也都要取。并且必然是取到第一个这样的物品，线段树二分即可。显然会使得 k←k−1。
否则，尽量取，同样线段树二分，最后也会使得 k←k−1。

「IZhO 2022」Zhylan.io

首先注意到，只需要考虑判断某个玩家能否从小到大攻击完所有其他玩家即可。
先排序。考虑计算 a1≤a2≤⋯≤an 的答案。
对于 ai，其能攻击所有 aj (j<i) 的条件是对于所有 j<i，有 ai≥aj−a1−⋯−aj−1+k。
而 j=i 时若不成立，则 ai 也无法攻击 ai+1。于是将限制改为 j≤i。这样这个条件也获得了单调性。
称为条件 1。

接下来，还要攻击所有 aj (j>i)，这只需 a1+⋯+aj−1≥aj+k，与 i 无关。称为条件 2。
再找到最后一次不满足这个条件的位置即可。

然后考虑倍增分块，考虑所有 [2j,2j+1)。
显见每一段内满足条件 1 的是一段后缀。因此先判断段末是否满足条件，然后二分第一个满足条件的位置即可。

对于条件 2，也可以倍增分块解决。每段内只需要判断至多两次。

时间复杂度 O((n+q)(logn+logV))。

「2019 ICPC Asia Xuzhou Regional」Yuuki and a problem

众所周知，考虑从小到大加数并维护可表示的极长前缀 [1,p]。若加入 x，且 x>p+1，则 p+1 就无法表示了。否则，可以使 p←p+x。

有一个暴力是每次把 ≤p+1 的数全部加入，这样每两轮至少会使 p 翻倍，从而就得到了很多个 log 的做法。

但这样的问题经常提示我们按值域倍增分块，考虑 p+1∈[2k,2k+1) 时，则要么在此块内终止，要么获得此块内所有数后进入下一块。

于是静态情况下（CodeChef FRBSUM, FJOI2016 神秘数, 2021 ICPC Asia Kunming Regional M）我们至少容易做到 O((n+q)(logn+logV))，运用分散层叠和线性 RMQ 可以做到 O(n+qlogV)。动态情况下朴素维护即可 O(nlogV+mlognlogV)，底层按 O(logV) 分块可使空间做到线性。

「Ynoi2003」博丽灵梦

一维区间数颜色是众所周知的。

二维，考虑将一维莫队，用不带增的回滚莫队则可以快速地找到前驱后继。
然后用二维分块（实质为 Θ(n0.25) 叉树套树）维护即可。

「Ynoi2079」riapq

序列分块。

散块受到的贡献是容易处理的。预处理各块内的贡献，和一个二维前缀和。

对于整块对整块的贡献，考虑先记录贡献系数，在查询时再计算贡献的具体值。这里也需要之前提到的二维前缀和。

对于左侧散块对整块的贡献，也可以转化成二维数点。

「Ynoi2004」rsxc

先考虑找合法区间。
按右端点扫描线，用 CF1100F 的前缀线性基 trick 可以 O(nlogV) 求出线性基大小的变化点。
同时对于每个 k 维护最小和最大的 l 满足 [l,r] 内的颜色数为 2k。
而我们知道一个集合 S 合法当且仅当 |S|=2k 且线性基大小为 k。

考虑算答案，注意到一般的数点难以优化，考虑合法区间的结构性质。
注意到对于每个 k 我们求出了 lk(r) 和 l′k(r) 表示所有 l∈[lk(r),l′k(r)] 的 [l,r] 是合法的。并且 lk(r),l′k(r) 关于 r 是单调的。

记询问区间为 [L,R]，答案是所有 r≤R 的 [lk(r),l′k(r)] 与 [L,R] 的交的长度和。

「Ynoi2005」rmscne

考虑每个询问 [l,r] 有长度连续的若干个后缀是合法的，考虑求出最短的合法后缀，并考虑对每个后缀维护出最短的合法前缀。
前者很容易线段树二分求得（不过似乎也可以用并查集），后者可以扫描 r，对每个 l 维护最大的 r′ 使得 [l,r′] 是 [l,r] 的合法区间。

「IOI2021」分糖果

很智慧啊。

考虑只有一个盒子的时候，那么我们其实只关心最后一次被 min 或 max 的时刻。
注意到，这段时刻一定是最长的后缀使得极差不超过盒子容量，可以线段树二分。
我们再求出最短的后缀使得极差超过盒子容量，可以判断出最后一次是 min 还是 max。

多个盒子只需扫描序列即可。

「HNOI2010」城市建设

有个一眼的线段树分治 + LCT 做法，不表。

考虑按时间分治，那么我们分别将区间内涉及的边的边权赋为 ±∞ 求 MST 可以约减问题规模到 O(r−l) 级别，然后就对了。

「Codeforces 603E」Pastoral Oddities

注意到度数均为奇数的图各连通块大小都是偶数。再冷静分析一下，连通块大小均为偶数的图一定存在一个边的子集满足度数为奇数。
并且连通块大小为偶数显然关于加边是有单调性的。
因此若只回答一组询问，我们只需要从小到大加边，直到满足条件。最后加的边就是答案。

那么一个做法是倒着做，双指针，然后用 LCT 维护删边。
也可以用线段树分治，因为线段树分治实际上还是可以当做一个在线的过程。

或者沿用 Link Cut Digraph（WD 与地图）的做法，整体二分计算答案，也是可以的。

「AHOI2013」连通图

有个很无聊的线段树分治做法，忽略。

找一棵生成树，然后可以证明不连通当且仅当所有覆盖每条边的非树边集合线性相关。
随机权值，暴力枚举子集或者线性基即可。

「NOIP2022」比赛

从左往右扫描，维护当前前缀的每个后缀最值。这里有一个颜色均摊，可以用单调栈实现。那么需要维护两个数列，支持区间覆盖或区间加，区间两数列乘积历史和。打标记即可。

「Ynoi2008」rdCcot

考虑找连通块的代表元。关于这张图，有一个很强的结论，就是在 BFS 序上前后三个点的连边具有传递性。因此代表元只需要取 BFS 最小的点，反之其若与 BFS 序在其之前的点无连边，自然就是一个代表元。
那么对每个 i 找出左边和右边第一个 BFS 序在其之前且与其有连边的点即可。可以点分治。接下来就是简单数点了，扫描线即可。

「CF1548E」Gregor and the Two Painters

类似的题。取 (ai+bj,i,j) 这个三元组最小的点为代表元。发现在题目给定的限制下，这样的条件很容易用数点刻画。

「2022 ICPC Asia Jinan Regional」Tree Distance / 「Ynoi2004」rpmtdq

考虑用树分治将需要计算的点对缩减到一定范围内，然后使用扫描线即可。

考虑点分治的一个阶段，(u,v) 的贡献是 du+dv，其中 d 是到当前重心的距离。注意到，我们可以摒弃不同子树的要求。
那么我们注意到，只需要对每个 u 找出左侧和右侧第一个 dv≤du 的 v。不难证明这样可以覆盖所有最小值 + 次小值的决策。

「北大集训 2021」小明的树

思博题。树的条件保证了连通块个数是点减边。美丽只需要未点亮的点构成一个连通块，因为根结点不会被点亮。
因此用一个线段树维护区间最小值和最小值的信息即可。

「PKUSC2021」逛街

操作非常颜色段均摊，考虑用平衡树描述颜色段变化的过程。注意维护最小值以支持删除。
询问就是楼房重建。

「BalticOI 2021 Day1」Inside Information

I

考虑线段树合并，由于合并操作恰出现 n−1 次，复杂度是正确的。

II

考虑点分治，容易刻画路径的条件。某个模拟赛题是这题去掉了 n−1 次的条件，但依然是树。因此需要使用点分治。

「洛谷 8959」「CGOI-3」灵气

I

类似上题的分析，仍然使用线段树合并。

II

考虑直接做。对向上的边的连通块进行树链剖分，并用一个序列描述其向下能到达的点。

「XX Open Cup, Grand Prix of Tokyo」Cookies

I

注意到 k 到 k+1 的答案仅有一个增量，因此我们考虑用二分转化为 01 序列上的问题。
考虑用 0 的数量 c 记录状态，插入 0 删最大值等价于 c←min(c+1,k)，插入 1 删最小值等价于 c←max(c−1,0)。
于是，这就是「IOI2021」分糖果。

II

很抽象的均摊做法。考虑形式化描述上面那个过程：初始时有 v，每次有操作 v>Bi→swap(v,Bi) 或 v<Bi→swap(v,Bi)。
相邻的同种操作可以合并成一个堆。接下来加上一个神秘的优化：若相邻的堆可交换则交换并合并。
哈哈，然后这就是对的了。感觉不如空子做法。

「XX Open Cup, Grand Prix of Tokyo」Yosupo's Algorithm

分治把有用的数对缩减到 O(nlogn) 级别然后二维数点。
若干年前的模拟赛搬了这题，好像当场写了个根号算法（

「Ynoi2009」rprmq1

选取一维对询问的矩形猫树分治，然后变成区间加区间历史最大值，细节比较多。

「Ynoi Easy Round 2022」超人机械

平凡题。三维偏序即可。

「Ynoi Easy Round 2022」虚空处刑

并查集。考虑快速找某种颜色的儿子，用线段树合并，底层用启发式合并 vector 或者链表维护即可。可以不支持删除，在查询的时候忽略错误的颜色。

「Ynoi2002」Goedel Machine

对于 √v 以内的质数，枚举所有幂计算贡献即可。
对于 √v 以外的质数，用莫队维护出现次数和贡献即可。

「Ynoi2011」成都七中

I

考虑 Kruskal 重构树，转化为给定两棵结点编号集合相同的树，询问两边各一个子树的交的颜色数信息。
在一边做静态链分治，转化为 O(nlogn) 次激活树上点，O(n) 次子树内对已激活的点数颜色。
考虑一种颜色的贡献是链并，用 set 维护 DFS 序处理链并，树状数组维护答案。

II

有一个结论：对于任意树上连通块，其中一定存在一个点使得其余点在点分树上是其后代。
那么我们只要离线，在点分治中遇到这个点时处理询问即可。注意到此时可以将 x 替换为分治重心，那么我们只需要记录每个点到分治重心的路径的编号 min 和 max，变成 2-side 矩形数颜色。可以扫描线。

「Ynoi2006」rldcot

静态链分治与 Link-Cut Tree 之争。

I

用静态链分治容易缩减有效点对到 O(nlogn)。

II

扫描线，在 Link-Cut Tree 上 access 维护每条边最后被哪个点访问。access 时发生的虚实边切换即为需要处理的修改，为每个颜色维护最晚出现的时间即可。

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

建出反串后缀树，然后就和上一题差不多了。

「洛谷 6292」区间本质不同子串个数

建出反串后缀树，然后就和上一题差不多了。

「洛谷 7361」「JZOI-1」拜神

建出反串后缀树，然后就和上一题差不多了。

「UR #20」机器蚤分组

找出结论，建出反串后缀树，然后就和上一题差不多了。

「Ynoi2005」vti

链并容易差分成若干个到 LCA 的链。考虑用括号序转化为区间查询，二次离线莫队即可。

「Ynoi2003」铃原露露

如果我们有限制 (a,b,c) 表示 a,b 的 LCA 是 c，容易扫描线。
考虑如何缩减有用点对，容易联想到静态链分治方法。

「CTS2022」普罗霍洛夫卡

颜色个数首先考虑扫描线，然后我们要支持区间 ai←ai+1，区间历史异或和。

不妨把一次修改看成是在时间轴的后缀上异或 ai⊕(ai+1)，然后我们想要维护这些后缀异或的贡献。容易发现我们只需要分修改时间的奇偶维护这个 ai⊕(ai+1) 即可。

但是好像还是比较困难，并没有本质改变。现在我们观察 x⊕(x+1)，我们不妨考虑对于每个 k，在修改 ai 之前，每有一个 ai 满足第其 0,…,k−1 位都是 1 就给这个位置的贡献异或一个 2k。

然后我们分块，设块长为 B，但是似乎还是难以维护。

注意到一个事实：ai 单调不降 / 不增，且相邻最多差 1，而我们知道一个数每加 2k 次 1 才会有 k 位以上的贡献，因此我们不妨取 B=2k，这样每个区间内只会有一种 ai 有高位的贡献，我们通过左右端点的 ai 就可以知道有没有。

但是我们还需要支持下放标记和整块修改，具体来说实现上有一些细节，对于每块我们需要维护：

• 在整块有 +c 的标记后再整体 +1，在 k 位以下的贡献是多少。

• 在整块有 +c 的标记后再整体 +1，给此时前 k 位有进位的位置打上修改标记。

• 在整块有 +c 的标记后再整体 +1，有多少个数进位到 k 以上（显然一个块内这样的数是相同的，因此我们相当于仅仅维护这种数的奇偶性）。

• 在整块有 +c 的标记后再整体 +1，给进位到 k 以上的数打上修改标记。

注意以上数组中的 c 可以对 2k 取模，并且贡献和修改互为转置（也就是下放标记的做法只需要把求贡献的做法反过来）。

我们以贡献为例：我们首先对于所有 i,j 求出前 i 位是 j 的数的奇偶性（注意到这里的状态数是 O(B) 的，只需要按照 i 从大到小递推），然后一个 (i,j) 如果加了 c≡2i−1−j(mod2i) 的话，就会有 2i 的贡献。当然这里我们不能枚举 c，注意到我们可以按照 i 从小到大，每次维护下标是 cmod2i 的答案，总共是 O(B) 的。

下推标记是类似的，不过需要注意它应该在旧的 ai 的基础上做（散块的单点修改也不能包含在内）。

如果取 k=12logn，可以有复杂度 O((n+m)√n)。

「Ynoi2005」rpxleqxq

显然首先二次离线莫队，然后要支持维护集合 S，O(n) 次插入 a，O(n√q) 次给定 b 询问 |{a∣a∈S,(a⊕b)≤x}|。

根据经典的经验，每个 a 能贡献到的 b 可以拆成 O(log) 个区间 [t2i,(t+1)2i)。不妨按照 B=2k 分块，对于 i<k 的区间暴力修改，对于 i≥k 的区间打整块标记，询问容易 O(1)。

令 V 是值域，取 k=12logV，有 O(n(√V+√q))。

「Ynoi2002」Optimal Ordered Problem Solver

以下描述的方向以常见的平面直角坐标系为准。

任何时刻点集形如一个阶梯轮廓线和一些没有操作过的点，注意我们容易通过二维偏序求出每个点进入轮廓线的时间。

对于某个点左下角的询问，我们分为轮廓线上和轮廓线外两部分。

轮廓线外的点，如果考虑三维偏序，会得到 log2 的做法。考虑观察，注意到某个点右上角的点一定和轮廓线无交（除非这个点首先在轮廓线左下方），因此我们拆成轮廓线外总点数减去某个点左上角，右下角，右上角的点数。前两者是一维时间和一维坐标的排序，第三者是两维坐标的偏序，都可以单 log。

然后我们只需要考虑维护轮廓线。容易想到用平衡树，卡常可以通过。精细实现也可以只使用线段树和 set。

「Ynoi2008」stcm

构造子树补信息。

题解区有个高赞的在 DFS 序上分治做法，本质上类似于链分治。

不妨还是考虑原汁原味的链分治，先走重链然后再对轻儿子带权分治即可。

「Ynoi2007」rfplca

这不是我们弹飞绵羊吗。

考虑分块，设块长为 B，维护每个点 i 的父亲 ai，和其第一个不同块的祖先 anci。容易通过这两个东西求出 LCA。

考虑维护之，虽然几乎不可维护，但是注意到对整块操作 B 次后块内一定会有 anci=ai，此时打标记即可。

「Ynoi2006」spxmcq

考虑固定 x 可以 DP gu=au+x+∑fv=umax(gv,0)。

不妨考虑转移图，即 gv>0 才连边 (u,v)，显然它是一片森林。这片森林上的转移就只需要 gu=au+x+∑(u,v)∈Egv。

考虑把 x 从小到大排序，那么森林只会加边不会删边，我们只需要考虑找到添加的边即可。设 su 表示森林里 u 的子树大小，hu 表示子树内的 au 之和，那么解 gu≥0 可得 x⋅su+hu≥0，即 x≥⌈−husu⌉。每次连边只会修改父亲所在连通块顶端点的这个值。

时间复杂度 O(nlogn)。

「Ynoi2008」rplexq

首先考虑 size2u−∑(u,v)∈Esize2v。

按儿子个数根号分治，设阈值 B。对于儿子个数 ≤B 的直接拆成 O(nB) 个二维偏序询问。

对于儿子个数 >B 的，如果对子树点跑小 Z 的袜子，复杂度仍然是错的。但有一个性质是，对于一棵树选前 k 大的儿子作为重儿子，则轻儿子的子树大小之和是 O(nlogk+1n) 的。因此我们取前 nd−1 (d∈(0,0.5]) 个重儿子，放进前一部分的偏序里做，轻儿子做小 Z 的袜子即可。

时间复杂度 O(n√m+n√n+m√n)。

「Ynoi2002」Adaptive Hsearch&Lsearch

考虑找支配对。

考虑网格化，取 L=20,21,... 作为边长，在相邻的格子里找支配点对。

不一定要显式地删除小的 L 贡献过的支配对，只需要钦定取相邻 O(1) 个即可。

因为修改常数太大了所以考虑分块 O(1)−O(√n)。

数据看起来不是很强，所以随便写写好像就能过了。

「CTS2022」燃烧的呐球

考虑 Boruvka，然后不妨考虑一个算法对于每个二元组 (xi,yi) 算出边权最小的 (xj,yj)，然后在算法里修改成维护最近的点和颜色不同的次近点即可。

注意 |S|+|T|≥|S⊕T|，因此我们把有祖先后代关系的算成没有关系的不会出问题。

开始分讨：

• x,y 至少有一边无关的是平凡的。枚举有关的那一边维护子树 / 祖先的最值即可。

• x,y 至少有一边满足 i 是 j 祖先的同样平凡，枚举另一边用线段树维护即可。后代需要线段树合并，祖先需要撤销。

• x,y 都满足 i 是 j 的后代的，需要把线段树换成全局平衡二叉树，同样需要支持撤销。

时间复杂度 O(nlogn+mlog2n)。

「Ynoi2009」rprmq1

两个 log 可以考虑猫树分治，拆成前后缀的询问，相当于线段树历史最值。注意修改要先类似线段树分治打在分治树上，以及可能需要先减后加，这样修改的总数是 O(mlogn)，总复杂度 O(mlog2n+(n+q)logn)。

也可以单 log，考虑按一维扫描线，然后相当于是区间加，区间询问一段时间区间的 max。考虑把询问的区间拆到线段树上，得到 O(mlogn) 个关键点，而时间区间 max 只需要在关键点之间 RMQ，因此只需要维护关键点之间的 max，类似线段树历史 max 进行维护即可。结合线性 RMQ 可以做到 O(n+(m+q)logn)。

「XXI Open Cup, Grand Prix of Nizhny Novgorod」Rectangle Painting

mex 比较难做，但是我们发现如果我们能知道线段树每个结点中，整个区间都是白色的高度的最小值，那么每个位置的 mex 就是其到根结点的这个值的 min。虽然和要求的东西最值方向不同，但是依然是能维护的。

进一步注意到每个高度只需要贡献到每个极大的，全是白色的结点即可，因此我们只要能维护出每个高度是白色的区间，然后在线段树上挂标记就可以。

对于每个高度维护一个 set，表示其没出现的极长区间。一开始全是 [0,2×105]，有修改的时候暴力分裂，删除中间的结点即可，类似颜色段均摊我们可以知道这里的复杂度是正确的。同时在线段树上需要支持区间插入一个数，删除一个数，求最值，用线段树套堆即可。

令 n=2×105，时间复杂度 O((n+q)log2n)。

「Ynoi2003」赫露艾斯塔

构造半平面莫队。

首先代价是不超过半平面所在的直线旋转平移经过的点数的。

随机撒 B 个点，然后先将每条直线向下平移到关键点，再在关键点上旋转即可。每条直线往下到第一个关键点期望经过 O(n/B) 个点，总复杂度 O(nB+nm/B)，取 B=Θ(√m) 即可做到 O(n√m)。

「JOISC 2019 Day2」两个天线

首先做两遍就可以丢掉绝对值，现在我们考虑 (j,i) (j≤i) 的贡献 Hi−Hj，且条件是 j∈[i+Ai,i+Bi],i∈[j−Bj,j−Aj]。

考虑枚举 j 扫描线，维护两个数组 a,b。当 j=i+Ai 时点亮 i，当 j=i+Bi+1 时熄灭 i，这部分贡献到 a 数组中；然后每个时刻将 [j−Bj,j−Aj] 内的 b 与对应位的 a 取最大值即可。查询即区间 b 的最值。

「IOI2018」排座位

对于一维，静态的情况下每个 k，我们有两种做法：

• 维护 0,…,k−1 出现位置的 max 减出现位置的 min 再减 k。这个值 ≥−1，且取到 −1 时合法。

• 维护 0,…,k−1 出现的边数，并用 k 减去它。这个值 ≥1，且取到 1 时合法。

注意到二维的情况下，交换时很难维护 max 和 min（尤其是还带有乘积），因此我们还是考虑一些局部的结构。

那么首先，它们需要是一个连通块；其次，连通块内部不能有拐角（包含 3 个 0,…,k−1 的数和 1 个其他数的 2×2 子矩阵）。

直接计数这两个东西的和。连通块我们使用欧拉公式处理。

不过题解区好像有一些更加简单的判据。感觉都差不多。

「Ynoi Easy Round 2022」堕天作战

注意到 <x 的会 <0，且今后一直会 −x，因此这部分我们可以使用一个树状数组维护。
剩下的部分就是，区间 >x 的 −x，维护区间和，区间最小值。这就是经典倍增分块 rgxsxrs。

不过 UT 给了一个更牛的做法。

考虑势能线段树，首先维护区间最小值，区间最小值 >x 的时候区间打标记，<x 的时候递归。可能需要特殊区分负数，但可以直接模 264 意义下自然溢出做。这部分递归的次数可以摊到操作后变成负数的数的个数上，是一个 log。

=x 的时候继续维护严格次小值，如果超过 2x 那么还是可以直接打标记，否则仍然递归。这部分每次会让次小值减半，因此这部分的复杂度是两个 log。

「UNR #5」诡异操作

除法是难以直接维护的，这部分我们直接均摊。按位与考虑维护每一位有几个 1，同时可以用来查询需不需要递归除。这个复杂度是 O(nlog2V+qlognlogV)，但是没救。

我们考虑每个结点维护的信息是一个 logV×loglen 的表格，(i,j) 格子对区间和的信息有 2i+j 的贡献，打标记是把一些行清零，信息上传是每一行做加法。

我们转置地对每一列开一个 V 大小的数压下每一行对应位置的值，然后上述操作都能简单维护。

区间按位与的复杂度显然是 O(qlog2n)，区间除法定位区间的复杂度也是 O(qlog2n)，对完整的区间进行修改的复杂度是 ∑loglenlogV=O(nlogV)，因此总复杂度是 O(nlogV+qlog2n)。

「ULR #2」Picks loves segment tree IX

如果离线，我们可以用 Trie 倒着维护，这样容易实现异或和 +1 操作。对于与和或操作，我们用 Trie 树合并实现打标记和标记的下传，需要精细实现。

只有异或和 +1 的时候，注意到任意操作可逆，可以得到一个做法，但是对后面的做法没什么用。

接下来有一个想法是用线段树维护任意的值经过每个结点会得到什么，每个结点维护一个 Trie，需要很多复杂的手法，感觉非常难写，大概可以获得高分。

但是正解和上面这些玩意都没啥关系。

我们直接思考怎么样延续每一位独立的性质，注意到 +1 会影响到第 t 位当且仅当做完这次操作之后 0,…,t−1 都是 0。因此考虑预处理出一些信息：

• fi,x 表示初始时最低位至少有 i 个 0，从第 x 个操作开始，到第 fi,x−1 个操作第一次又至少有 i 个 0。

• gi,x 表示初始时最低位恰好有 i 个 0，从第 x 个操作开始，到第 gi,x−1 个操作第一次又至少有 i+1 个 0。

这两个数组可以互相递推。

询问的时候，记 i 是当前的 0 的个数，先一直跳 gi 直到 i≥t，然后我们只需要一直跳 ft 即可。对每个 ft 我们建出一棵树，然后树剖一下维护答案。

「UNR #7」鸽子收费站

这个问题的维度比较多，规范一下称呼：编号维、时间维、操作维。

考虑扫描编号维，再扫描每个编号对应的时间维，然后按操作维顺序维护所有询问的答案。那么我们在一个询问编号维的起点和终点插入和查询结果，然后扫描每个编号对应的时间维的时候做一下颜色段均摊。发现问题形如，维护一个序列支持以下操作：

• 单点修改，单点查询。

• 将下标在 [l1,r1]，值在 [l2,r2] 的元素赋值为 r2。

那么我们还是尽可能考虑势能线段树，在当前结点区间里有两个需要赋值的值的时候才递归。但是这个东西很难判断，我们只能考虑线段树套平衡树。

但是仍然存在一个问题是，只有一种值需要修改的时候难以打标记。

我们继续大力地处理：让平衡树上每个结点不存储真实值，而是记录它在父亲平衡树对应的位置。细节不想抄了，代码也不是很想写。