线段树与平衡树专题

虽然这个也是为了准备而写的一个 blog 就对了。

BAS 1: red

BAS 2: orange

ADV 1: yellow

ADV 2: green

EXP: blue

MST: purple

Re:MST: black

P2042 维护数列 Master

题目大意

写一个程序，要求维护一个序列。支持：

插入、删除、修改、区间翻转、区间求和、区间求最大子段和操作。

任何时候中数列个数 。操作次数 。

解答

因为有插入、删除、修改和区间查找操作，可以很自然地想到平衡树。

前面几个是好操作的。翻转操作就先把这个区间提出来，然后给他打一个翻转 tag。

求和、求最大子列和就使用区间合并就可以做完了。

P5482 不等式组 Expert

题目大意

旺汪与旺喵最近在做一些不等式的练习。这些不等式都是形如 的一元不等式。当然，解这些不等式对旺汪来说太简单了，所以旺喵想挑战旺汪。旺喵给出一组一元不等式，并给出一个数值。旺汪需要回答的是 时成立的不等式的数量。聪明的旺汪每次都很快就给出了答案。你的任务是快速的验证旺汪的答案是不是正确的。

---

输入第一行为一个正整数 ，代表接下来有 行。

接下来每一行可能有 种形式：

1. Add a b c：表明要往不等式组添加一条不等式 。
2. Del i：代表删除第 条添加的不等式（最先添加的是第 条）。
3. Query k：代表一个询问，即当 时，在当前不等式组内成立的不等式的数量。

注意：一开始不等式组为空， 均为整数，且保证所有操作均合法，不会出现要求删除尚未添加的不等式的情况，但可能重复删除同一条不等式。

。

解答

可以被转化为 或是 或是 。然后这个东西可以用树状数组维护。

P7706 文文的摄影布置 Expert

题目大意

尽管图片非常多，但幸运的是，文文已经将它们排成了一列，从左到右分别编号为 ，文文选取的三张图片，应该是一个长度为 的子序列。（不妨设选取的照片的序号为 ，则必须要有 ）。

此外，文文给每张照片定了一个吸引度 与大小 。

因为报纸版面太大会降低读者的兴趣，于是选定两张照片 后，规定必须选择最小的 。

形式化地说，规定 ，其中需要满足 。

摸清了照片价值的计算，文文会告诉你共 个操作，可以分为以下三种：

• 1 x y ：照片的吸引度发生变化。文文要将 修改为 。
• 2 x y ：照片的大小发生变化。文文要将 修改为 。
• 3 l r ：文文打算利用素材库的第 到第 张中的图片，你要告诉她 的最大值（ ）。

。

解答

这个可以使用线段树维护。合并类似于区间合并。

而因为 应该在两个 中间，所以我们维护每一个区间的 ，。还有每一个区间的 ，。合并就和区间合并差不多了。

P4036 火星人 Master

题目大意

火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。

比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：

序号 1 2 3 4 5 6 7 8 9 10 11 
字符 m a d a m i m a d a m

现在，火星人定义了一个函数 ，表示：该字符串中第 个字符开始的字串，与该字符串中第 个字符开始的字串，两个字串的公共前缀的长度。比方说，

在研究 函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出 函数的值；同样，如果求出了 函数的值，也可以很快地将该字符串的后缀排好序。

尽管火星人聪明地找到了求取 函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取 函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取 函数的值。

---

第一行给出初始的字符串。第二行是一个非负整数 ，表示操作的个数。接下来的M行，每行描述一个操作。操作有 种，如下所示

1. 询问。语法： ， , 均为正整数。功能：计算 限制： , 当前字符串长度 。
2. 修改。语法： ， 是正整数， 是字符。功能：将字符串中第 个数修改为字符 。限制： 不超过当前字符串长度。
3. 插入：语法： ， 是非负整数， 是字符。功能：在字符串第 个字符之后插入字符 ，如果 ，则在字符串开头插入。限制： 不超过当前字符串长度

。

解答

有插入操作就用平衡树。

判断两个字符串相等就使用哈希。

那么，我们就使用平衡树来维护哈希值。然后查询最长公共前缀就可以使用二分。

具体地，每次二分一个长度 ，然后看 和 是否相同。这玩意可以将其从线段树拎出来来获得哈希值。若两个哈希值相同，则爽。

P3215 括号修复 Master

题目大意

一个合法的括号序列是这样定义的：

1. 空串是合法的。
2. 如果字符串 S 是合法的，则(S)也是合法的。
3. 如果字符串 A 和 B 是合法的，则 AB 也是合法的。

现在给你一个长度为 的由(和)组成的字符串，位置标号从 到 。对这个字符串有下列四种操作：

• Replace a b c：将 之间的所有括号改成 。假设原来的字符串为：))())())(，那么执行操作 Replace 2 7 ( 后原来的字符串变为：)(((((()(。
• Swap a b：将 之间的字符串翻转。假设原来的字符串为：))())())(，那么执行操作 Swap 3 5 后原来的字符串变为：))))(())(。
• Invert a b：将 之间的 ( 变成 ) ，) 变成 (。假设原来的字符串为：))())())(，那么执行操作 Invert 4 8 后原来的字符串变为：))((()(((。
• Query a b：询问 之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的 ( 变成 ) 或 ) 变成 (。注意执行操作 Query 并不改变当前的括号序列。假设原来的字符串为：))())())(，那么执行操作 Query 3 6 的结果为 ，因为要将位置 的)变成(并将位置 的(变成)。

。

解答

假设设右括号的权值为 ，左括号权值为 。设词根 表前缀， 表后缀，那么要求求一个区间的：。

而翻转（Swap）操作和反转（Invert）操作用线段树是实现不了的，所以这里要使用平衡树维护。

那么，就要维护每一个区间的基本信息加上 。那么：

• Replace 操作就是区间打一个修改 tag。并且赋值 。
• Swap 操作就是区间打一个翻转 tag。并且交换 变量。注意还要交换左儿子和右儿子指针！
• Invert 操作则是区间打一个反转 tag。并且 。而且还要给 Replace 操作的修改 tag 也取反。

在 pushdown 操作时，不同的操作顺序似乎会对结果有影响。这里使用的是先 Invert，次 Replace，最后 Swap。

P6617 查找 Master

题目大意

给定 个垃圾桶，你需要维护一个数据结构，支持以下操作：

• 1 pos val 表示将 第 个垃圾桶里的垃圾的编号换成 ；

• 2 l r 询问在 内是否存在垃圾编号和为 的 两个 垃圾桶。

其中 表示异或运算， 表示在 此次询问之前，答案为 Yes 的个数。

对于每个操作 2，若存在请输出 Yes，不存在请输出 No。

值得注意的是，对于所有询问， 为 同一个数。

。

解答

首先，容易想到维护所有点的最大前驱（前驱指的是与这个值互补（即加和为 的值的位置）。然后查询去检查这个区间的最大值看结果是否 。这个可以用线段树维护。

若不修改还好，修改就比较麻烦。如果暴力修改，那么复杂度将会是 级的。

观察性质。会发现是由一段段 组成的。然后会发现，只有前两个 这个才是有用的，其它后面的 都是无用的。最开始就先给这些位置的前驱赋为 。每次修改的时候就最多关乎以下 5 个位置：

1. 这个数的后面，与这个数相同的数；
2. 这个数的后面，与这个数互补（加和为 w）的数；
3. 这个数本身；
4. 修改后的、这个数的后面，与这个数相同的数；
5. 修改后的、这个数的后面，与这个数互补（加和为 w）的数。

可以先把这 5 个数拎出来，然后再一起修改。这个可以使用 set 维护。只不过比较麻烦。

P11071 Distorted Fate AT Lv.17.4 Expert

题目大意

给定一个长度为 的数组 ，你需要完成以下 次操作。

1. 1 l r x 将 异或上 。

2. 2 l r 求：

   $$(\sum_{i=l}^r\bigcup_{j=l}^i A_j) \bmod 2^{30}$$

   其中 表示按位或。

空间限制：

，。

INITALIZING……
SCANING……
CONNECTING……__PhigrOS Client Login
TIME_OUT!
CONNECTING……__Unknown
SUCCESS!
————————
……九……鸟……
……鸠……！
……喂？
…听得到吗？
鸠?![SIGNAL LOST]

某七字母音乐游戏

解答

因为这是一道关于区间的按位或和按位异或的题，所以可以考虑拆位。

因为空间的限制，我们可以先把询问离线，然后算每一位对答案的贡献，最后把它们加起来就是总答案了。

那么因为是区间修改，所以可以用线段树来维护。

然后对于答案，我们要维护什么？因为是 ，所以当第 个数为 ，那么 。所以我们只要维护区间最早的为 的数的位置即可。

然后对于异或操作，当异或 时区间明显不变，否则这个区间的所有 。那么就可以再维护一个区间最早的为 的位置，然后执行操作时，就交换这两个位置。

T512613 Distorted Fate 加强版 U-TA-GE

题目大意

同 P11071。此版强制在线。

空间限制 。

解答

要求强制在线的话，那么就不能使用上一道题的离线算法了，要使用在线算法

首先，看这个式子，可以发现这个式子的后半部分 是会随着 的增长而变大的，但是由于这是按位或运算，变大的次数最多只有 次。所以我们可以先拆位，然后看这一位是什么时候变成 的。然后后面肯定就全部都是 了，就把贡献算上。

不过这个“找区间出现最早的 ”操作需要对每一位建一棵线段树，即建 棵线段树。然后如果是一般维护的话就是线段树存出现位置最早的点，但是由于这道题空间限制太小，所以要换一种维护方式。

我们既要维护区间出现最早的 位置，又要支持异或操作，考虑其实区间我们其实关心的是这个区间有没有 。然后找位置就在线段树上二分即可。然后对于异或操作，我们可以维护这个区间是否为全 或是否为全 。这两个东西可以转化为区间或和区间与。然后若区间与的结果是 ，或者区间或的结果是 ，就修改状态。否则就不修改。然后因为是区间异或，所以也一样要打 lazytag。这样也省下了空间，一个 node 只需要 个 bool 变量。

P3586 LOG(Logistyka) Master

题目大意

维护一个长度为 的序列，一开始都是 ，支持以下两种操作：

1. U k a 将序列中第 个数修改为 。
2. Z c s 在这个序列上，每次选出 个正数，并将它们都减去 ，询问能否进行 次操作。

每次询问独立，即每次询问不会对序列进行修改。

解答

看这个查询操作，可以将序列分为两部分： 的数和 的数。根据贪心，这些 的数一定要选。然后看剩下的 的数。那么还需要选的数就是 减去 的数的个数。记其为 。再即 的数之和为 。

那么首先，可以看出很明显的一点，当 ，则不行，因为数都不够选。那么当 时，那么，因为剩下的所有数 ，所以数的个数一定 。于是，我们从最大的数开始选，就一定存在解。

然后用平衡树来维护、并求出 和 即可。

P8496 [NOI2022] 众数

题目大意

对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入，在本题中请以题面中给出的定义为准。

一开始给定 个长度不一的正整数序列，编号为 ，初始序列可以为空。这 个序列被视为存在，其他编号对应的序列视为不存在。

有 次操作，操作有以下类型:

• ：在 号序列末尾插入数字 。保证 号序列存在，且 。
• ：删除 号序列末尾的数字，保证 号序列存在、非空，且 。
• ：将 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 。数据保证对于任意 ， 是一个仍然存在的序列，，且拼接得到的序列非空。注意：不保证 互不相同，询问中的合并操作不会对后续操作产生影响。
• ：新建一个编号为 的序列，其为 号序列后顺次添加 号序列中数字得到的结果，然后删除 对应的序列。此时序列 视为存在，而序列 被视为不存在，在后续操作中也不会被再次使用。保证 、、序列 在操作前存在、且在操作前没有序列使用过编号 。

和 ，分别表示数列的个数和操作的次数，保证 、。
假定 代表输入序列长度之和，则保证 、。
假定 代表所有操作 需要拼接的序列个数之和，则保证 。

解答

对于这种绝对众数，首先我们就应该想到摩尔投票。

Q：摩尔投票是什么算法？

一个求众数非常高效的算法。暴力求众数 （排序），摩尔投票求只需要 。

首先，我们定一个 。表示众数的剩余次数。再定 为众数是什么。我们每一次加一个数 ，若该数 ，则让 。然后当 时，那么原来那个众数肯定不合法，就推举 成为新的众数，。如果存在绝对众数，那么最坏的情况 都大于 。

而若不存在绝对众数，那么 是啥都有可能。所以最后要判一下出现次数是否大于一半。

贴一个有绝对众数的序列判绝对众数的代码（也就是若没有说明一定有，那么最后要特判）：

cin>>n;
int cnt = 0, num = 0;
for(int i=1;i<=n;i++){
 int x; cin>>x;
 if(x == num) cnt ++;
 else{
     cnt --;
     if(cnt < 0) cnt = 1, num = x;
 }
}
cout<<num<<'\n';

我们可以使用动态开点权值线段树来存储每一个序列中每一个数出现几次。然后因为摩尔排序显然是有结合律的，然后这个权值线段树也可以存储每一个序列摩尔排序之后的众数的 和它的 。之后把所有玩意拎出来然后结合并判断是否大于序列的一半，然后 3 操作就解决了。

1 操作是容易使用动态开点权值线段树解决的。2 操作就需要找到每一个序列最后一个元素，需要用链表解决。4 操作就是线段树合并 + 链表合并，即可过。

细节比较多，注意特判链表长度 和绝对众数长度 int 溢出的情况！

P3765 总统选举 Master

题目大意

黑恶势力的反攻计划被小 C 成功摧毁，黑恶势力只好投降。秋之国的人民解放了，举国欢庆。此时，原秋之国总统因没能守护好国土，申请辞职，并请秋之国人民的大救星小 C 钦定下一任。

作为一名民主人士，小 C 决定举行全民大选来决定下一任。为了使最后成为总统的人得到绝大多数人认同，小 C 认为，一个人必须获得超过全部人总数的一半的票数才能成为总统。如果不存在符合条件的候选人，小 C 只好自己来当临时大总统。为了尽可能避免这种情况，小 C 决定先进行几次小规模预选，根据预选的情况，选民可以重新决定自己选票的去向。

由于秋之国人数较多，统计投票结果和选票变更也成为了麻烦的事情，小 C 找到了你，让你帮他解决这个问题。

---

秋之国共有 个人，分别编号为 ，一开始每个人都投了一票，范围 ，表示支持对应编号的人当总统。

共有 次预选，每次选取编号 内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜。如果没有人获胜，则由小 C 钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有 个人决定将票改投向该次预选的获胜者。

全部预选结束后，公布最后成为总统的候选人。
，，，。

解答

如何查找动态的区间内一个数出现的次数？使用平衡树维护每一个数出现的位置即可。

CF643G Choosing Ads 3200?

题目大意

• 给定一个长度为 的序列和一个整数 。
• 有 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 的数。
• 输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 。
• ，。

解答

而这道题就是摩尔投票的拓展：当绝对众数的定义为 的情况。

那么也可以用与摩尔投票相似的方法：

1. 记录长度为 的 和 数组。
2. 当一个新数 在 数组出现过时，将这个 对应的 自加。
3. 否则，若存在一个空位置，即存在 的位置，就用 补上这个 ，并赋其 。
4. 否则，将所有数的 全部 。

做完之后记得要 check 一下这些 是否合法。（不过对于这道题来说不用。）

那么接下来我们证明这个方法为什么是对的。我们使用反证法，假设一个出现次数 的数 最后没有在 里面。分两种情况（这里令 ）：

1. 若这个东西根本就没有被加到 数组里面过，那么每遍历一次 ，里面所有数的 都要减一次 。那么统计一下所有数的出现次数和至少为：

   。与原有题意相矛盾，舍去。

2. 若这个东西被加到 数组里过，但是后面被杀出去了。那么在加入时， 会使原本数组内 个数加上自己的 个数，共 个数的出现次数 ，在被删除时，后面的数也会使 个数的出现次数 。那么光这些的出现次数就已经是 了。也与原有题意相矛盾，舍去。

所以最终属于答案的数一定会留在 里面。

而也很明显的，这道题的摩尔投票拓展也存在结合律。所以也可以像上一道题一样，使用线段树来维护信息。

P8543 纯粹的复仇女神 Master

题目大意

给定一个长度为 的序列，序列中每个元素是一个二元组 ，分别表示颜色与权值。

现在有 次询问，每次给出一个区间 ，求：

$$\max\limits_{k=1}^n \left\{\min\limits_{l\le i \le r,c_i=k} a_i\right\}$$

特别地，如果 内没有颜色为 的值，后面的部分定义为 。

对于全部数据，保证 ，，，。

解答

我们先对特定的一个 进行考虑：颜色为 的某个元素 是在什么时候成为颜色 的 值的？

我们画个图，举个例子：

我们设 的范围为 ， 所在的位置为 ，那么这个序列 值为 的情况就是 。

所以，对于询问中 的返回 ，那么这个要怎么维护？我们可以将询问离线，然后搞一棵 线段树，当 使 区间覆盖 ，然后当 时就撤销区间覆盖。这可以使用标记永久化 +（multiset 或可删除堆）实现。

然后现在 变多了，但是方法没变。依然是对于每种颜色独立的找出每一个元素影响的区间范围，然后和之前一样修改/撤销、查询。

P5416 [CTSC2016] 时空旅行 Re: Master

题目大意

2045年，人类的技术突飞猛进，已经找到了进行时空旅行的方法。小 R 得到了一台时空旅行仪，他想用它调查不同时空中人类的发展状况。

根据平行时空理论，宇宙中存在着很多独立的时空，每个时空在下一个时间点还会分化出若干个不同的时空。宇宙是一个三维空间，人类使用空间直角坐标系来描述空间中的一个位置，三维坐标分别是 。

我们假设在初始的时空（编号为 ）中，人类存在于地球上（地球的坐标为 ），其他的时空都是从一个现有的时空发展而来的。一个时空发生一个时间之后会发展成为另外一个时空（原来的时空不发生任何变化）。会影响小 R 的时间包括两类：

1. 人类殖民了一个新的星球，该星球的状态变成“已被殖民”。
2. 人类放弃了一个已被殖民的星球，该星球的状态变成“未被殖民”。

每次进行时空旅行时，小 R 会先选定一个时空。在这个时空中，人类已经殖民了一些星球。小 R 只要到达该时空中任意一个已被殖民的星球，就能调查人类的发展状况。

小 R 的时空旅行仪出现了一些问题，调整 坐标的按钮坏掉了，因此到达点的 坐标被固定了（每次旅行的 坐标值可能不同）。与此同时，他仍能任意调整到达点的 坐标和 坐标。

这个问题大大增大了小 R 的花费：因为时空旅行没有花费，但在太空中航行却需要花钱；同时，在不同星球进行调查也可能会产生不同的费用。

假设小 R 将时空旅行的终点设为 ，他要进行调查的星球为 ：如果 与 的欧几里得距离为 ，那么他太空航行的花费就是 ；又如果星球 上进行调查的费用为 ，那么小 R 此次调查的总花费就是 。

现在给定小 R 每次旅行到达的时空以及时空旅行仪上固定的 坐标值，请你计算出小 R 每次旅行完成调查的最小总花费。

输入的第一行包含三个非负整数 ， 表示平行时空数量，这些平行时空的编号为 到 的整数，初始时空的编号为 。 表示小 R 进行的时空旅行的次数， 表示在地球进行调查的花费。保证 。

接下来 行，依次描述平行时空 到 ，其中第 行分两种情况：

1. ：表示编号为 的平行时空由编号为 的时空发展而来，人类殖民了一个编号为 的星球，该星球的坐标为 ，在该星球进行调查的花费为 。数据保证给出星球的编号不重复，且 ；保证 。
2. ：表示编号为 的平行时空由编号为 的时空发展而来，人类放弃了编号为 的星球。数据保证该星球在编号为 的时空中处于被殖民的状态；保证 ，即地球一定不会被放弃。

上述两种情况中，各参数均为正数，相邻整数之间均用一个空格隔开；均保证 。保证不会出现上述两种之外的情况。

接下来 行，每行表示小 R 进行的一次时空旅行。每行包括两个正数 和 ，表示小 R 到编号为 的平行时空进行了一次时空旅行，时空旅行仪上的 坐标被固定为了 。保证 ，。

输出 行，分别表示每次旅行完成调查的最小总花费。

解答

观察分析发现，题目中的 完全无用。所以题面用人话来说就是给你一堆点，每一个点有一个坐标 和权值 ，有基于前面某个版本的加点和删点操作，每一次给定 和 ，要你求版本 的 。

我们将后面那个式子拆开，就变成了 。因为 可以在后面加上去，所以对于每一个点的贡献就相当于是 。对于每一个点， 是已知的， 是未知的。所以可以把贡献看成 ，然后求 的最小值。

这个可以使用凸包维护，也可以像我一样使用李超线段树维护线段维护（其实是我不会凸包（（（，具体用李超树怎么维护，就是因为操作是形成一棵树，每一个版本都是基于前面某一个版本的，所以可以预处理出每一个星球被殖民的区间。（可能一个星球会有多个区间被殖民）然后放到线段树上，使用线段树分治做。因为线段树上，版本 是基于 上的，所以可以使用可持久化李超线段树来做。

但是这样是会 MLE 的。所以这颗李超线段树可以使用下标回收策略。不用的下标就收回来。具体来说：

void bfs(int x, int l, int r, int lstrt){
    int nowidxcnt = lcsegtr.idxcnt;
    ...
    int mid = l+r>>1;
    bfs(x<<1, l, mid, lstrt), bfs(x<<1|1, mid+1, r, lstrt);
    lcsegtr.idxcnt = nowidxcnt;
}

并且，只是这样还不够。在预处理区间的时候也要使用更加精细的实现，尽量少开 vector：

void dfs(int x){
    if(ope[x].op == 1){
        lst[ope[x].id] = dfn[x];
    }else{
        segtr.insert(1, 1, n, lst[ope[x].id], dfn[x]-1, ope[x].id);
        lst[ope[x].id] = dfnout[x]+1;
    }
    for(int i=h[x];i;i=edge[i].nxt) dfs(edge[i].to);
    if(ope[x].op == 1){
        segtr.insert(1, 1, n, lst[ope[x].id], dfnout[x], ope[x].id);
    }
}

CF1083D The Fair Nut’s getting crazy 3500?

题目大意

给定一个长度为 的序列 。你需要从该序列中选出两个非空的子段，这两个子段满足：

• 两个子段非包含关系。
• 两个子段存在交。
• 位于两个子段交中的元素在每个子段中只能出现一次。

求共有多少种不同的子段选择方案。输出总方案数对 取模后的结果。

需要注意的是，选择子段 、 与选择子段 、 被视为是相同的两种方案。

。

解答

首先，对于一个给定的区间 ，这两个子段交为 ，那么这两个子段的选法有多少种？

我们定 为距离 最近的、位置小于 的、值等于 的位置。 为距离 最近的、位置大于 的、值等于 的位置。并且定义 为 ， 为 。（所以其实 和 都可以预处理。）

那么对于交 的答案就是 。交合法的条件也就是交内所有的数都只出现过一次。

那么对于左端点 ，我们要找到 使交 都是合法的并且 尽量大。这个可以使用双指针扫，因为很明显的，当 增加时， 是不降的。然后我们就要求对于 的 。

这个怎么求呢？把式子展开：原式 。第二项的 可以使用等差数列。其它三项的 都可以使用 lazytag 线段树来维护。

但是怎么维护呢？区间 不会要使用 Segtree beats 吧？其实我们发现，对于每一个 ， 是单调不降的。所以我们可以将区间取 转化为区间赋值。我们可以使用线段树上二分或者单调栈预处理修改区间，来处理出是每次是修改哪个区间。 同理。

还有一点，为了好维护， 端点建议从 开始遍历到 。因为这样可以每次都是新增一个元素来取 ，而不是删除原来的元素。

CF1083C Max Mex 2900?

题目大意

有一次，格里莎发现了一棵树（无循环的连通图），树根位于节点 。

但这棵树并不只是一棵树。从 到 的整数的排列 写在节点上，一个数字 写在节点 上。

格里沙喜欢自己发明一些奇怪而有趣的问题，但并不是总能解决这些问题，所以你需要帮助他处理关于这棵树的两种类型的查询。

让我们定义一个函数 ，其中 是一个非负整数集合，作为不包含在这个集合中的最小非负整数。

假设 是这棵树上的一条简单路径。因此，我们将位于 上的节点的索引定义为 。

定义 为集合

那么查询就是

1. 对于两个节点 和 ，交换 和 。
2. 找出所有可能的 中 的最大值。

。

解答

这道题我们可以将 看作 是否出现在一条链上。我们可以将这个化为数 是否出现在一条链上。发现这个东西是可以合并的，所以可以使用线段树维护。

看 4 个点 是否出现在一条链上的方法其实是枚举所有的情况，看 是否等于 即可。所有的情况其实只有 6 种，所以 pushup 操作是 完成的。（可以预处理欧拉序求 LCA）

查询就在线段树上二分，若左半部分可以就跳右半部分去，否则跳到左半部分里面查。

P6272 没有人的算术 Re: Master

题目大意

万物初始之前，宇宙是无边无际混沌的黑暗，只有上帝之灵穿行其间。

上帝对这无边的黑暗十分不满，就一挥手说:“要有光”，于是世间就有了光。从此，世间 就有了昼与夜的交替。这是上帝创世的第一天。

第二天，上帝仍不满意眼前空洞的景象，就一挥手说：“要有零”。于是世间出现了第一个数：。

第三天，上帝对只有 很不满意，就一挥手说：“要有非零数”。于是上帝开始创造新数，每个新数用一个已经创造出来的数的有序对表示，即：

$$x = (x_L, x_R)$$

于是世间出现了 。到了晚上，各种各样千奇百怪的数在大地上奔腾。
（注：上帝造的这个 “数” 与普通的自然数、有理数之类的不同，这种数是以如上所述的方式递归定义的，总是数对里面是数对，拆分到最后会得到不可再拆的 ）

第四天，上帝看到各个数不分彼此，就一挥手说：“要有区别”。于是为了区分每个数，上帝定义等于：

1. 。

2. 对于任意 ，若 且 ，则 。

3. 对于任意 ， 当且仅当满足以上条件之一。反之记作 。

第五天，上帝看到各个数乱成一团，就一挥手说：“要有序”。于是为了比较每个数，上帝定义小于：

1. 对于任意 ，若 ，则 。
2. 对于任意 ，若 ，则 。
3. 对于任意 ，若 且 ，则 。
4. 对于任意 ， 当且仅当满足以上条件之一。反之记作 。

在此基础上定义小于等于： 或 。容易发现：

1. 。
2. 。
3. 或 。

进而定义：

1. 。
2. 。

至此万物欣欣向荣，和睦一堂。

第六天，由于之前沉迷与算术而忘记去造核酸和蛋白质，所以上帝没办法造人。但是上帝不甘心，就一挥手说：“要有跳蚤”，于是用泥巴捏出了神奇生物跳蚤。

上帝用五天的时间造出天地万物，又在第六天造出了唯一的生命——跳蚤。上帝看到天地万物井然有序、生生不息，自己造的跳蚤正在开心地和数学玩耍，很高兴，便决定把第七天作为休息的日子。

跳蚤每天的生活很简单。一天开始时，他会取一个长度为 的数组 ，初始时均为 。

接着他会不断地做下列两件事之一：

1. 在头脑中产生三个正整数 ，然后把 重新赋值为 。特别地，如果 或 也是合法的，这不会导致错误，因为跳蚤总是先默默算出 再给 赋值。

   保证 。

2. 在头脑中产生两个正整数 ，然后计算 中的最大值。

   保证 。

跳蚤当然知道怎么做啦！但是他想考考你……

。

解答

首先，如果递归比较的话，那就是特大暴力做法，肯定过不去，然而，这个 数对是可以用数来表示的。具体来说，我们给每一个数对 放在平衡树上。然后因为是平衡树，所以大小关系显然吧。之后，我们给每一个节点设置区间权值 和点权值 （使用 double 类型）。我们先给根节点 传一个区间权值 ，然后就设根的点权值为 。之后，递归到左、右儿子，赋左儿子区间值为 ，右儿子区间值为 ，然后递归处理。

但是这样很可能会遇到退化成一条链的情况。这种情况下精度不够。所以要控制树高在合适范围内。这个时候就要使用重量平衡树。

引用博客：关于重量平衡树的瞎扯

重量平衡树一般使用替罪羊树或者 Treap 实现。这里使用 Treap。

插入节点 insert(&rt, x, double L, double R) 的时候比较 和 的优先级。如果 的优先级小于 的优先级，那么合并。否则分裂、插入，然后暴力重构权值信息。

最后维护最大值使用一棵线段树实现。

CF2023F Hills and Pits 3500?

题目大意

在一个地势起伏的沙漠城市中，市政府计划购置一辆自卸卡车来平整道路。道路按从左到右的顺序被分为 段，编号为 到 。第 段道路的初始高度是 。如果某段道路的高度高于 ，则需要自卸卡车从中移走部分沙子；如果低于 ，则需要用沙子填平。所有路段在开始时的高度都不为 。

当卡车在第 段时，它可以取走 单位的沙子，使该段高度减少 ，或者可以填入 单位的沙子（前提是车上至少有 单位沙子），使该段高度增加 。

卡车可以从任一段开始工作。移动到相邻的下一段或上一段需要花费 分钟，而装填和卸料的时间则可以忽略不计。卡车有无限容量，最初是空车。

你的任务是计算出将每个路段高度调整为 所需的最短时间。注意，完成所有操作后，车上可能仍残留沙子。你需要单独解决每个从 到 段的沙子调整问题，且只能使用指定段内的沙子。

，且

保证所有测试用例中 的总和以及 的总和不超过 。

解答

容易发现，如果 ，则无解。当 时，若不符合上一句的情况，则答案为 。

因为题目中要让我们把每一个点都走一次的。假设我们定了 ，最坏情况肯定就是走 次，走过去再走回来。那么我们假设起点为 ，终点为 （），那么最优的走法之一肯定就是 。

我们定 为 。这里需要满足 ，否则这种走不了。容易发现 这一部分肯定已经被补完了。然后 部分同理。现在分析 的部分。假设 均 ，，那么就说明我们可以使用 这个点来补充 的部分。也就是说，中间多走的步数就是 。那么总答案就是 。因为我们要求答案的最小值，所以就相当于是求最大子段和了。

但是这个 是基于 计算的，所以不能直接搞。我们定全局前缀和为 ，可以发现 ，所以可以将询问离线处理，然后按照 排序，然后线段树实时更新。

上面说的是 的情况， 的情况就是把整个序列的前缀和和询问倒过来就可以了。

后记

这篇博客似乎已经废了。那天根本就没有讲。

算了摆了，cnblog 上博客链接贴在这儿，博客密码 みるく。