高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
Luogu分析考虑每个数的贡献。假设 $x$ 在 $[l,r]$ 中出现了 $c$ 次，则有 $2^{r-l+1}-2^{r-l+1-c}$ 个子序列包含 $x$，所以其贡献为 $x(2^{r-l+1}-2^{r-l+1-c})$。考虑把出现次数相同的放到一起，即求出每种出现次数对应的数的和。显然可以直接莫队。注意到出现次数最多只有 $\mathcal{O}(\sqrt{n})$ 种，所以我...
Luogu分析一个显然的想法是我们每次选能选的最短的一根。但是这样会有一些问题，就是选了最短的之后两边的就不能选了，然后答案会偏大。这个其实比较好解决。假设当前最短的长度为 $l_u$，左右两边的长度分别为 $l_L$ 和 $l_R$，那么我们在选 $u$ 之后加一个长度为 $l_L+l_R-l_u$ 的候选项，表示删掉 $u$ 而选左右两个。这样子就是对的了。用堆维护以上过程，双向链表维...
BZOJ分析只考虑选的点都在线段下方的情况，在线段上方的情况可以通过将纵坐标取反一样的做。首先考虑线段的纵坐标无限大的情况，显然线段的左右边界会卡在相邻的两个颜色相同的点之间。那么只需要将所有点按横坐标排序，维护一下上一个某种颜色的点，再用树状数组维护区间内点的个数即可。现在把线段向下移动，假设现在纵坐标刚好比某个点 $u$ 的纵坐标小 $1$，此时线段左右边界会卡在上一个和 $u$ 颜色相...
Luogu分析考虑到如果两个点之间没有边，那么这两个点一定会分在一个集合里。也就是说我们要求的实际上是补图的连通块。但是直接连边去求边数是 $n^2-m$ 级别的，显然存不下。考虑一个很暴力的想法：每次找一个还没有找连通块的点，然后 BFS 找连通块。具体就是扩展 $u$ 时，先标记 $u$ 的所有出点，然后所有没有找到连通块的没有被标记的点都和 $u$ 在一个连通块中。问题就是怎么维护还没...