猫耳开关 - 洛谷保存站

[喵。](https://www.wxmp3.com/mp3/a51344d512b0c8c40c899a202fa9ca8e.html)

---

[Top Cluster](https://qoj.ac/problem/8235?locale=zh-cn)
> * 题意：多次查询邻域点权 mex，其中**点权两两不同**。
> 
> 二分答案，每次问 $\max_{i=0}^{mid}\mathrm{dis}(i,x)$，那么即为点集最远点，容易 $O(n)$ 预处理，每次 $O(1)$ 查。\
> 总复杂度 $O(q\log n)$。

[[Ynoi2006] rldcot](https://www.luogu.com.cn/problem/P7880)
> 考虑 dsu on tree，在 LCA 处计算点对 $x,y,d$ 的数量，其中 $x$ 新合并的节点，$y$ 是 $x$ 左边/右边的第一个点，$d$ 是 LCA 的深度。我们得到 $O(n\log n)$ 个点对。\
> 那么我们每次询问 $l\le x\le y\le r$ 的 $d$ 的颜色数量，按 $y$ 扫描线，维护每个颜色的最后一次出现的 $x$，在 $r$ 处查询即可。复杂度 $O(m\log n+n\log^2n)$。

[[SDOI2017] 树点涂色](https://www.luogu.com.cn/problem/P3703)
> 操作一：暴力合并，用树剖+线段树复杂度均摊 $O(\log n)$。\
> 操作二：查 $val_u+val_v-2val_{lca}+1$。\
> 操作三：线段树区间最大值。
>
> 复杂度 $O(n\log ^2 n)$。

[[KTSC 2024 R2] 病毒](https://www.luogu.com.cn/problem/P11241)
> 建立 $2n$ 个中转点，那么我们可以连 $u\rightarrow w\rightarrow w'\rightarrow v$ 的边。\
> 优化建图，考虑点分树，我们每次对于 $u$ 和其点分树祖先 $t$，要连 $t$ 子树内距离 $\le d$ 点的边，那么我们可以对于所有的点分树上 $t$ 建 $siz_t$ 个点，然后向对应深度的点连边，然后做前缀和，每次向中专点连边即可。\
> 边数是 $O(n\log n)$ 的。

[[NOI2021] 轻重边](https://www.luogu.com.cn/problem/P7735)
> 神秘转化：操作变为将 $a$ 到 $b$ 的路径染上一种没有出现过的颜色，然后重边为两个端点颜色相同的边。\
> 考虑对于查询，将重边分为树剖上的重边和轻边。\
> 维护是个毛毛虫修改。

[[Ynoi2008] rplexq](https://www.luogu.com.cn/problem/P6782)
> **这个题好难呜呜呜，没补完**\
> 对度数根号分治，查 ${s_u}^2-\sum_v {s_{v}}^2$。
> * 对于度数小于 $\sqrt n$：\
>   那么我们暴力给出 $\sqrt n$ 个查询问子树大小，这是个二维数点，一共 $n$ 个点，$m\sqrt n$ 个询问。\
>   对于修改使用 $O(\sqrt n)-O(1)$ 的修改即可。
> * 对于度数大于 $\sqrt n$：\
>   考虑莫队，类似小 Z 的袜子，但是复杂度是 $O(siz_u\sqrt q)$ 的，就不对。\
>   我们希望每个 $u$ 的做莫队的节点总个数不超过 $n$，那么复杂度就是正确的。\
>   按照 dfs 顺序处理询问，对于 $u$ 将子树分为

[[ZJOI2019] 语言](https://www.luogu.com.cn/problem/P5327)
> 考虑一个暴力：对于 $u$，求出其对应 $v$ 的连通块。\
> 那么这类似于维护一个虚树，线段树合并做。

[[NOI2014] 购票](https://www.luogu.com.cn/problem/P2305)
> sst, i rebuke thee.\
> 首先考虑没有 $l$ 的限制，且树是一个链，那么我们可以用 dfs，可持久化李超维护 dp。\
> 然后对于不是链的情况，考虑线段树套李超处理。这里空间复杂度是 $O(n\log n)$ 的，因为李超空间是 $O(n)$ 的。\
> 最后考虑 $l$ 的限制。考虑出栈序，我们在最浅的满足 $l_u$ 的限制的那个祖先 $t$ 的出栈序和 $u$ 的出栈序之间进行查询。因为我们还没有遍历不在 $t$ 和 $u$  之间的节点，所以查询到的是对的。\
> 时间复杂度 $O(n\log^2 n)$，空间复杂度 $O(n\log n)$。

[[Ynoi2011] 成都七中](https://www.luogu.com.cn/problem/P5311)

[Iqea](https://www.luogu.com.cn/problem/CF936E)

正在渲染内容...