Day 1 CF1270H Number of Components
发现极大的连通块形如 \([l,r]\) 区间形式，其中满足 \(\min\limits_{k=1}^{l-1}a_{k}>\max\limits_{k=l}^ra_k\)，而且 \(\min\limits_{k=l}^ra_k>\max\limits_{k=r+1}^na_k\)。
所以区间 \([l,r]\) 的右端点满足 \(\min\limits_{k=1}^ra_k>\max\limits_{k=r+1}^na_k\)。将 \(\ge a_r\) 标 \(1\)，\(<a_r\) 标 \(0\)，那么序列形如 \(111\cdots 100\cdots 0\) 的形式（前面一共有 \(r\) 个 \(1\)）。这是充要条件。
由于数列的数互不相同，所以可以尝试枚举 \(a_r=v\)，合法的 \(r\) 个数即满足序列形如 \(111\cdots 100\cdots 0\) 的 \(v\) 的个数，即满足 \(01\) 序列中只有一对相邻形如 \(10\) 的串的序列的个数，这对相邻的 \(10\) 对应唯一的 \((a_r,a_{r+1})\)。
所以对于一对 \((a_i,a_{i+1})\)，满足其在 \(01\) 序列中形成形如 \(10\) 串的 \(v\) 满足 \(v\in [\min(a_i,a_{i+1}),\max(a_i,a_{i+1}))\)。所以我们给区间 \([\min(a_i,a_{i+1}),\max(a_i,a_{i+1}))\) 上的数全部 \(+1\)，表示这对 \((a_i,a_{i+1})\) 会给这段区间的 \(v\) 的 \(01\) 序列贡献一个 \(10\)。
最后我们需要求出 \(10\) 个数为 \(1\) 的序列的个数。考虑到离散化后对于所有的 \(v\)，其 \(01\) 序列中至少都会有一对 \(10\)，直接维护最小值以及最小值个数即可。
Day 2 Ynoi2015 我回来了
介绍个最劣解 \(O(m\sqrt n+n\sqrt n+n\alpha(n)\ln n)\) 做法。
首先令 \(b_i\gets a_i-1\)，区间 \([l,r]\) 的答案就是：
考虑如何动态维护后面那个式子。我们对每一个 \(k\in [1,n]\) 维护一个大小 \(n/k\) 的 bitset，代表所有 \(b_i/k\) 的值，最低位的 \(0\) 就是 \(k\) 对应的 \(\text{mex}\)。
加入一个 \(b_i\) 的时候考虑所有 \(b_i/k\) 的值，不难发现只有 \(O(\sqrt n)\) 种取值，于是可以分成 \(O(\sqrt n)\) 个区间修改，每次修改形如 \((l,r,x)\)，代表往 \(l\) 到 \(r\) 每个 bitset 中插入数 \(x\)。
因为 \(n\) 个 bitset 的总大小不超过 \(n\ln n\)（调和级数），所以如果我们每次修改 \((l,r,x)\) 都能找到一个是 \(0\) 的位，把这位换成 \(1\)，并不访问别的 \(1\) 的话，这个复杂度就是正确的。于是不难想到对每个 \(x\) 维护一个并查集，这样就可以从一个位置 \(p\in[l,r]\) 迅速跳到下一个第 \(x\) 位为 \(0\) 的 \(p'\) 了。
然后我们在跳 \(p\) 的时候需要动态维护 \(p\) 的 bitset 的 \(\text{mex}\)，由于只有插入没有删除，这显然可以均摊 \(O(n\ln n)\) 维护。得到这个 \(p\) 的权值后，就只需要一个单点修改 \(O(1)\) 的数据结构来维护 \(m\) 次区间和查询了。显然分块可以做到 \(O(1)-O(\sqrt n)\)。于是就得到了 \(O(m\sqrt n+n\sqrt n+n\alpha(n)\log n)\) 的优秀做法。
Day 3 BalticOI 2020 小丑
整体二分。
有个小技巧，就是可以把存边的数组往后复制一遍，然后删去区间 \([l,r]\) 就相当于保留区间 \([r+1,l+m-1]\) 的边。于是只需要解决这么个问题：
给定一张 \(n\) 个点 \(m\) 条边的无向图，\(q\) 次询问，每次只保留区间 \([l,r]\) 的边，问是否是二分图。
乍一看有点像 Cnoi2019 须臾幻境？但是其实有不用 LCT 的做法。
考虑令 \(f_l\) 表示最小的 \(p\) 使得 \([l,p]\) 区间不是二分图。显然 \(f\) 具有单调性，即 \(\forall i\le i',f_i\le f_{i'}\)。只需要求出所有的 \(f_i\)，就可以直接根据 \(f_l\) 是否 \(\le r\) 判断是否是二分图了。
由于 \(f\) 的单调性，不难想到整体二分。令 \(S(l,r,v_l,v_r)\) 表示处理 \(f_{l},f_{l+1},\cdots, f_{r}\)，并且 \(v_l\le f_l\le f_r\le v_r\)。令 \(\text{mid}=\frac{l+r}{2}\)，于是只需要求出 \(f_{\text{mid}}\) 即可：用可撤销并查集从 \(\text{mid}\) 开始加边，第一个使得图不是二分图的位置就是 \(f_\text{mid}\)。
为了保证复杂度，需要在分治之前将 \((r,v_l)\) 的边先加进并查集中。然后就没什么细节了。
复杂度 \(O(m\log m\log n+q)\)，整体二分复杂度写假的是小丑。
Day 4 SDOI2016 游戏
令 \(\text{lca}(u,v)=w\)，\(s_u\) 为 \(u\) 到根的距离（随便指定一个根），考虑 \(u\to w\to v\) 的路径修改：
- \(x\in \{u\to w\}\)：\(n_x\gets a(s_u-s_x)+b=-a\cdot s_x+(b+a\cdot s_u)\)。
- \(x\in \{w\to v\}\)：\(n_x\gets a(s_u+s_x-2s_w)+b=a\cdot s_x+(a(s_u-2s_w)+b)\)。
考虑树链剖分，将修改拆分到 \(O(\log n)\) 条重链中。由于重链中 \(\text{id}\) 连续，这是关于 \(\text{id}(u)\) 的一次函数形式。李超线段树维护区间线段 \(\min\)，在区间中插入线段即可。
李超树区间插入（非全局）是 \(O(\log^2n)\) 的（分成 \(O(\log n)\) 个区间后分别再在每个区间中插入），所以复杂度是 \(O(n\log^3n)\) 的。不知道为啥能过。
Day 5 CERC2014 Pork barrel
考虑 Kruskal 算法的过程，即边权从小到大依次加入边，每条边连接两个连通块。很重要的性质是每次加入的边边权单调不降。
于是权值 \([L,R]\) 内的边组成的最小生成树，相当于从权值为 \(L\) 的边开始跑 Kruskal，取所有 \(\ge L\) 的边组成的最小生成树，树上所有边权 \(\le R\) 的边的边权之和。
将边从小到大排序，如果对于每个边权 \(L\)，求出边权 \(\ge L\) 的一段后缀的边组成的最小生成树，就能够通过一些可持久化手段维护出此时边权 \(\le R\) 的边的边权之和。
若已经求出 \(L'\ge L\) 的最小生成树（\(L'\) 是 \(L\) 值域上的后继）\(T'\)，考虑新增 \((u,v,L)\) 这条边，得到新的最小生成树 \(T\)：
- 若 \(u,v\) 在 \(T'\) 中联通，找到 \(u\to v\) 简单路径上边权最大的边，删去这条边，然后加入 \((u,v,L)\)。
- 若 \(u,v\) 在 \(T'\) 中不连通，直接加入 \((u,v,L)\)。
注意到 \(n\le 10^3\)，这允许我们在 \(O(nm)\) 的时间内求出这 \(m\) 棵最小生成树。
由于 \(T'\to T\) 的边权变化是 \(O(1)\) 的，于是只需要一个支持单点修改，区间求和的可持久化数据结构。使用可持久化权值线段树即可。
复杂度 \(O(nm+(m+q)\log W)\)。