C. Colorful Segments 2
考虑最小的分组数量，可以先按左端点排序，然后每次贪心地找到前面一个最大右端点 \(r_j < l_i\) 的组加入。
考虑计数，还是同样地按左端点排序，那么假设现在有 \(k\) 个组，每个组最大右端点是 \(g_i\)（没有元素则 \(g_i = 0\)），那么每次可以选择一个 \(g_j < l_i\) 的组并且把 \(g_j\) 更新为 \(l_i\)。注意到我们不需要关心具体的 \(g_j\)，只用关心 \(g_j < l_i\) 的数量。由于 \(l_i\) 是单增的，所以所有 \(g_j < l_i\) 的组 \(j\) 本质相同。那么就是每次查询 \(g_j < l_i\) 的数量，并且将其减 \(1\)，并插入一个 \(r_i\)，可以用堆模拟。复杂度 \(\Theta(n \log n)\)。
E. Sensors
由于恰好有 \(1\) 个点的线段是有用的，且每个点不会被重新加入，那不妨考虑每次删除点的时候快速找到所有从 \(>1\) 个变成 \(1\) 个的线段，和从 \(1\) 个变成 \(0\) 个的线段。
从 \(1\) 个变成 \(0\) 个是好维护的，只需要把 \(1\) 个的线段插入到那个点的 vector 中，删除的时候直接减去所有的贡献即可。
从 \(>1\) 个变成 \(1\) 个时，线段的左右端点恰好跨越一个点。设当前剩下的点坐标是 \(pos_1 < pos_2 < ... < pos_m\) 那么不妨用一个 multiset 维护每个 \(r_j \in [pos_i, pos_{i+1} - 1]\) 的 \(l_j\)，删除 \(pos_i\) 时直接把 \(st_{pos_i}\) 合并到 \(st_{pos_{i-1}}\)，并访问 \(st_{pos_{i-1}}\) 和 \(st_{pos_{i+1}}\) 最大的 \(l_j\) 更新即可。复杂度 \(\Theta(n\log^2n)\)。
考虑更优秀的复杂度，把每个线段插入到线段树上的 \(\log n\) 个节点，然后对于每个线段维护它所在的所有节点中点个数 \(=0,=1,>1\) 的节点个数，当更新一个节点 \(u\) 时，若 \(sum_u \le 1\) 就访问所有这个节点上的线段更新即可。复杂度 \(\Theta(n\log n)\)。
G. Cosmic Travel
差分转化为 \(x \le m\) 的第 \(k\) 大和，那么套路地枚举 \(x\) 和 \(m\) 的 lcp 下一位，在 trie 上模拟前这些位（若这一位是 \(0\)，则先看 \(siz_{ls}\)，不够就到 \(rs, k \leftarrow k - siz_{ls}\)），然后拆成 \(\Theta(\log V)\) 个询问一个子树异或任意数（不能超过这个子树能表示的最大数）的第 \(k_i\) 大和。注意到这个东西是与询问无关的，设 \(dp_{i,j}\) 为 \(i\) 子树异或任意数的第 \(j\) 大和，状态数量为 \(\Theta(n \log V)\) 的（每个叶子统计 \(\Theta(\log V)\) 次）。
这里为了方便，可以把和设为只看子树里的这些位的和，类似地模拟转移即可。
复杂度 \(\Theta((n+q)\log V)\)。
L. Intersection of Paths
考虑对于一个 \(k\)，有那些点可能成为并的一个端点，考虑每一条边 \((u,v)\)，如果删掉这条边后 \(\min(siz_u,siz_v) \ge k\) 这条边就合法，那么 \(u,v\) 就合法。那么假如不考虑更改边的话，答案就是只取这些点组成的虚树（一定是原树的一个联通块）的直径。
考虑 \(k\) 不同，并且加入更改边，由于大的 \(k\) 对应联通块一定被小 \(k\) 对应的完全包含，那么可以直径从小到大扫描线，每次从 \(k \to k + 1\) 时，把 \(\min(siz_u,siz_v) = k\) 的边删掉（更改边权为 \(0\)）。
那么就是要实现动态修改边权，查询直径。考虑在欧拉序上做，每次遍历到 \(u\) 在 dfs 序后加入 \(u\)，遍历 \(u\) 的 每个 儿子回来后再加入 \(u\)。然后就是要找到一个区间 \([l,r]\) 的 \(\max\limits_{l\le L \le a \le R\le r} dep_L + dep_R - 2 \times dep_a\)，其中 \(a\) 肯定是 \([L,R]\) 中 \(dep\) 最小那个。于是线段树上维护区间信息 \(ans,ansl,ansr,maxd,mind\) 对应上述答案、\(\max\limits_{L \le a} dep_L - 2 \times dep_a\)、\(\max\limits_{a \le R} dep_R - 2 \times dep_a\)，最大和最小 \(dep\)。合并时 \(ans = \max(ans_{ls},ans_{rs},ansl_{ls}+maxd_{rs},maxd_{ls}+ansr_{rs})\)，\(ansl = \max(ansl_{ls},ansl_{rs},maxd_{ls} - 2\times mind_{rs}),ansr=\max(ansr_{ls},ansr_{rs},maxd_{rs} - 2\times mind_{ls})\)。
显然支持修改，复杂度 \(\Theta((n+q)\log n)\)。
标签：Provincial,Shandong,le,log,Contest,dep,线段,pos,ls From： https://www.cnblogs.com/MiniLong/p/18447323