Day1
模拟赛T1 Cyaneous Rain
首先需要有 \(\mathcal O\!\left(n^2\right)\) 的算法。这可由如下性质得到：未建的电车站一定构成一段区间。
证明：考虑从左到右的电车站 \(a,b,c,d,e\)，其中 \(a,e\) 已建。考察 \(b,c,d\) 的修建顺序：
- \(cbd\to 2e-2a\)
- \(bcd\to 3e-a-b-c\)
- \(dcb\to c+d+e-3a\)
若 \(3e-a-b-c\) 和 \(c+d+e-3a\) 均不大于 \(2e-2a\)，则可导出 \(b\ge d\)，而这是不可能的。因此 \(cbd\) 绝非最优解。
换句话说，每次一定选最左侧的或最右侧的未修建的电车站修建。
接下来在差分数组上重写问题，就是构造一个长度为 \(n+1\) 的序列 \(c_i\)，每个元素为 \(a_i-a_{i-1}\)（\(i\in[1,n+1]\)）每次只能选最左或最右的，使得 \(\sum i\times c_i\) 减去 \(c_{n+1}\) 最大。
这个 \(c_{n+1}\) 比较特殊，考虑枚举 \(p\)，使 \(c_i=a_p-a_{p-1}\)。这样可以看作是 \(p\) 左侧的序列与 \(p\) 右侧的序列做某种归并类操作。不妨记左侧序列为 \(x_1,x_2,\dots\)，右侧序列的倒序为 \(y_1,y_2,\dots\)。除去不难计算的内部贡献后，\(x_i\) 的贡献为它前面 \(y\) 的个数乘上 \(x_i\) 的结果，\(y_i\) 的贡献为它前面 \(x\) 的个数乘上 \(y_i\) 的结果。
若 \(x,y\) 两序列均单调不减，则直接从小到大归并是最优的。证明考虑若 \(x_i>y_j\)，则 \(\dots,x_i,y_j,\dots\) 比 \(\dots,y_j,x_i,\dots\) 多 \(y_j-x_i\)，前者绝对不优。
若存在 \(x_i>x_{i+1}\)，则最优解一定把它们放在一起。证明：设 \(y_1+\dots+y_k=S\)，则有如下三种情况：
- \(x_i,y_1,y_2,\dots,y_k,x_{i+1}\) 的贡献为 \(S+kx_{i+1}\)；
- \(x_i,x_{i+1},y_1,y_2,\dots,y_k\) 的贡献为 \(x_{i+1}+2S\)；
- \(y_1,y_2,\dots,y_k,x_i,x_{i+1}\) 的贡献为 \(k(x_i+x_{i+1})\)。
可以发现后两种都不优于第一种的情况由于 \(x_i>x_{i+1}\) 是绝不可能成立的。
因此遇到 \(x_i>x_{i+1}\)，可以直接把它们改为两个 \(\frac{x_i+x_{i+1}}{2}\)，不影响结果。\(y\) 类似。这样问题就转化到了 \(x,y\) 均单调不降的情况了，从小到大归并即可。
但是这还仅仅是单个 \(p\) 的情况。对于原题，需要枚举 \(p\)，动态修改 \(x,y\)。将序列中一段相同值的元素压在一起，每段存储值和个数，这样修改是均摊 \(\mathcal O(n)\) 的。同时维护它们归并后的序列，这可以上一棵平衡树，时间复杂度为 \(\mathcal O(n\log n)\)。
P7603 [THUPC 2021] 鬼街
减半警报器 revisited。
由鸽巢原理 \(\sum_{i=1}^ka_i=S\Longrightarrow \exists a_i\ge\left\lceil\frac{S}{k}\right\rceil\)，每次对于一个监控器，把这个监控器的阈值平分到所有它监控的房间中。若更新后仍没有响，那么设之前的阈值为 \(B\)，则新值一定不超过 \(\left(\frac{k-1}{k}\right)B\)。这样每个监控器被检测的次数至多为 \(\log_{\frac{k}{k-1}} B\)。
后来有了二进制警报器。
对于每个警报器维护一个阈值 \(h\)。当 \(a\gets a+w\) 时称 \(a\)“经过了”\([a+1,a+w]\)。那么当 \(a\) 经过 \(2^h\) 的倍数时报警。如果所有元素不报警就可以使阈值超过限制就令 \(h\gets h-1\)。这样是单 \(\log\) 的。
GYM104065B/QOJ8035 Call Me Call Me
首先肯定是能选就选。所以问题变成每次把一个人点亮，我需要知道新的可以点亮的人有哪些，这确实很像减半警报器。
但是这个限制对一般的减半警报器来说太大了，因为区间长度是 \(O(n)\) 的。来先做个弱化：
P4215 踩气球
限制了 \(k_i=r_i-l_i+1\)。做法是把一个区间拆开放到线段树上，每次对线段树上一个节点 pushup 时若发现其中均已被点满，则枚举所有拆在这个点上的区间，逐个判断。这样就是对每个拆开的区间都遍历一次，因此时间复杂度为 \(\mathcal O(n\log n)\)。
对于原题，类似地考虑把减半警报器拆到线段树上。每次 pushup 时暴力枚所有区间，未触发就全部更新一次。那么实际上和鬼街是差不多的，只不过离散的只能放到每个点上，而区间可以拆成 \(\log\) 个。用二进制警报器，时间复杂度两个 \(\log\)。
zak 说把线段树改成 \(\log\!\left(\sqrt{n}\right)\) 叉的再上二进制警报器可以得到更优的时间复杂度 \(\mathcal O\!\left(\frac{n\log^2n}{\log\log n}\right)\)。
但是这样常数太大了，CF 过不去啊。有没有更快的做法？有的兄弟有的。
如果 \(k_i\le\sqrt n\)，则直接全部放进线段树，每次暴力 \(k_i\gets k_i-1\) 去更新。考虑操作分块，每 \(\sqrt n\) 次修改后重构，把所有 \(k_i\le\sqrt n\) 的区间放进线段树，但要保证一个区间最多放进线段树一次。线段树中的区间要时刻删去已经点亮过的（\(k_i=0\)）。这样，每个区间最多被改 \(\sqrt n\) 次，单次时间复杂度 \(\mathcal O(1)\)，总的时间复杂度就是 \(\mathcal O(n\sqrt n)\)。
P7880 [Ynoi2006] rldcot
找支配对。树上启发式合并，对于小树找到任一个数与外界小于它的最大值组成的对，以及任一个数与外界大于它的最小值组成的对。这样对数是 \(\mathcal O(n\log n)\) 的。
然后问题变成每次求 \(x\ge l, y\le r\) 的所有点 \((x,y)\) 的颜色数。可以将 \(x\) 一维离线扫描线下来，然后 \(y\) 就只需要维护一个最靠前的颜色 \(u\) 的位置 \(p_u\)。总共只需要单点加和区间查询，使用树状数组即可。
时间复杂度 \(\mathcal O(n\log^2 n+m\log n)\)。
Day2
P10834 [COTS 2023] 题 Zadatak
把正方形看成一个个“环”，从内到外第 \(i\) 个环的大小为 \(4\!\left(i^2-(i-1)^2\right)\)，且只有全黑和全亮两种可能。
把连续的环压成一个区间 \([l,r]\)，做线段树合并，需要维护黑色大小以及取反 tag。
可以发现，在合并两个正方形时，若存在全黑或全白的区间，它合并另外任意一个区间都是容易的。这种区间没有左右儿子，所以这样做相当于是减少了很多无用节点，只有在每次 pushdown 时可能会新增一层。因此这样的时空复杂度依然都是一般的 \(\mathcal O(n\log n)\)。
P4065 [JXOI2017] 颜色
一个随机化做法：对每个位置赋一个 \(\left[0,2^{64}\right)\) 的值，在满足同色位置的异或和为 \(0\) 的基础上尽量随机，这样满足题意的区间的异或和为 \(0\)，不满足题意的区间的异或和有极大概率不为 \(0\)。
一个确定性做法：考虑从左到右扫右端点，实时维护满足条件的左端点。
记录一个颜色 \(c\) 的第一次出现和最后一次出现的位置，分别记作 \(f_c\) 和 \(l_c\)。那么当右端点为 \(i\) 时，\(i\) 左侧最大的满足 \(l_{a_j}>i\) 的位置 \(j\) 是不能选的。以及，对于 \((j,i]\) 之间的位置 \(k\)，\((f_k,l_k)\) 是不能选的。
上面的所有限制都可以模拟。\(j\) 可以用堆维护，禁选的位置可以在线段树上维护，总体的时间复杂度为 \(\mathcal O(n\log n)\)。
P3587 [POI 2015] POD
这题类似，随机化做法可以加一个双指针，确定性做法可以加一个线段树二分，时间复杂度均不变。
P11622 [Ynoi Easy Round 2025] TEST_176
\(x\to\max(x,a_i-x)\) 相当于是如下的函数：
那么需要维护一棵平衡树，支持取反与加某个数，以及两棵平衡树的合并。但是这里的合并交集大小不再是 \(\mathcal O(1)\) 的，所以需要平衡树有交合并。
对于两棵值域有交的平衡树 \(x,y\)，设 \(x\) 根的随机权值比 \(y\) 小，合并的方式如下：
- 将 \(y\) 按 \(x\) 根的值分裂为两棵树 \(l,r\)。
- 将 \(x\) 的左儿子与 \(l\) 递归地做有交合并，同理 \(x\) 的右儿子与 \(r\) 合并。
- 若 \(y\) 中有与 \(x\) 根的值相同的节点，它们的答案肯定与 \(x\) 根一样，需要用并查集合并，否则时间复杂度是假的。然而也可以设一个第二权值，规避掉这种情况。
这样的时间复杂度可以证明是两个 \(\log\) 的。
唯一还需要注意的点是对于一个负数 \(a\)，\(\left\lfloor\frac{a}{2}\right\rfloor\) 不能写 a / 2 而要写 a >> 1。
AT_cf17_final_j Tree MST
史诗经典 Boruvka 题。
对着做，发现每次扩展，对于每个 \(x\) 找到最小的向外的边相当于找不在同一个连通块中的最小的 \(w_y+dis_{x,y}\)。若没有“不在同一个连通块中”这个限制，那么可以简单地换根 dp 得到。有了限制后，需要同时维护最小值和次小值，并限定它们必须来源于不同的连通块。这样若最小值与 \(x\) 在一个连通块中时，次小值就是正确的了。
由于 Boruvka 有 \(\mathcal O(\log n)\) 轮，每一轮找边的时间复杂度为 \(\mathcal O(n)\)，所以总时间复杂度为 \(\mathcal O(n\log n)\)。