Ynoi 选择性食用

简单没写清单

• [Ynoi Easy Round 2017] 由乃的 OJ：裸树剖
• [Ynoi2013] 大学：。。。
• [Ynoi Easy Round 2016] 炸脖龙 I：会拓展欧拉定理就会了
• [Ynoi Easy Round 2022] 虚空处刑 TEST_105：维护儿子信息（“邻域维护父亲一定死”）
• [Ynoi Easy Round 2022] 超人机械 TEST_95：记录最前和最后的下标就可以做到本质不同
• [Ynoi Easy Round 2023] TEST_90：矩阵维护历史和
• [Ynoi Easy Round 2025] TEST_176：平衡树模板
• [Ynoi2006] spxmcq：直接做
• [Ynoi Easy Round 2016] 镜中的昆虫：每次修改前驱点变化 O(1) 个，CDQ
• [Ynoi2003] 铃原露露：支配对，扫描线

正文

[Ynoi2010] y-fast trie

$i+j\ge C$ 是好做的，另一种朴素想法是维护所有 $i+j$ 对，数量级太大。对症下药，考虑一些类似支配对的东西：如果对于 $i$ 来说 $j$ 最优，对于 $j$ 来说 $k$ 最优，那么 $j+k$ 必定优于 $i+j$，最后只要记录互相选择的答案。每次修改只会涉及最多 $2$ 个元素的修改，$\mathcal O(n\log n)$。

[Ynoi2010] Fusion tree

打个儿子 tag，Trie +1 trick。

[Ynoi Easy Round 2025] TEST_34

区间修改不好做，差分得到 $b$，发现原来线性基等价于 $b_{l+1}\sim b_r$ 和 $a_l$ 构成的线性基。暴力是 3log 的，使用 zak 在 WC2025 介绍的方法：取区间的 $T=\log qV+\epsilon$ 个子集，最后这 $T$ 个子集异或和的值构成的线性基可以代替原来的，2log，证明在下面。

[Ynoi Easy Round 2023] TEST_107

答案取值三种情况：把一种值从左边切掉，从右边切掉，或者从两边切掉，都是二维数点。

[Ynoi2002] Goedel Machine

把最大公约数的贡献拆到所有质因子上。即对于所有 $p\in \mathbb P,k\in \N^+$，所有 $p^{2^{\sum[a_i\bmod p^k=0]}-1}$ 的乘积即为答案。考虑莫队，$p\le \sqrt V$ 的预处理，剩下的总共信息量 $\le n$，可以暴力算。

[Ynoi Easy Round 2024] TEST_132

如果 $x$ 的的值域很小，每次查可以暴力枚举 $x$；如果 $y$ 很小，每次修改就可以暴力。结合起来就得到了 $\mathcal O(n\sqrt{n\log V})$ 的做法，观察到 $v^{2t}\bmod p=v^{2t\bmod (p-1)}\bmod p$，对每个 $p$ 预处理光速幂，这里分四段预处理就是 $\mathcal O(nv^{\frac 1 4})$，可以接受。

[Ynoi2018] 五彩斑斓的世界

分块，如果把每块的 $\max$ 看成势能那么势能不降。散块直接重构，剩下对每个整块维护并查集，如果操作的数 $v>\dfrac \max 2$，那么暴力把 $[v,\max]$ 的值减掉，否则把 $[0,v]$ 的值合并，并打一个 $\times-1$ 的 tag。

[Ynoi Easy Round 2020] TEST_100

和上面题一样，这里分块预处理经过每一块的值域映射。

[Ynoi Easy Round 2021] TEST_68

找出全局最大异或对，那么除了两个点对应祖先答案不是最大值其他都是，对祖先暴力。

[Ynoi2005] rmscne

对 $r$ 扫描线。线段树每个点 $i$ 存储最小的 $j$ 使得 $[i,r]$ 出现的颜色数等于 $[i,j]$ 出现的颜色数，修改是区间覆盖。查询的时候要找到最大的位置 $p$ 使得 $[p,r]$ 出现的颜色数等于 $[l,r]$ 出现的颜色数，可以线段树二分，一个比较巧妙的做法是维护一个并查集，每次扫描到一个数 $r$ 把上一个相同颜色出现的位置 $t$ 合并到 $t+1$，代表 $t$ 已经被 $r$ 代替了，那么只要查询 $l$ 所在的并查集。

[Ynoi2006] rldcot

找支配对，对编号启发式合并，合并之后相邻两个即为支配对，扫描线。

[Ynoi2077] stdmxeypz

普通分块是容易的，有个简单一点的写法是把子树拍成 dfn，并对 dfn 分块，再根号分治就对了。

[Ynoi2008] rplexq

令 $S(u,l,r)=\sum\limits_{v\in \text{subtree}(u)}[l\le v\le r]$，那么答案为 $\dfrac 1 2(S(u,l,r)^2-\sum\limits_{v\in \text{son}(u)}S(v,l,r)^2-[l\le u\le r])$。如果度数 $\le B$，直接全局扫描线，平衡一下是 $\mathcal O(n\sqrt n+qB)$ 的。$>B$ 的可以对每个点上的询问莫队，复杂度是 $\mathcal O(n\sqrt q)$ 的。后面的瓶颈在于指针移动次数，如果我们子树大小前 $B$ 大的全局做，后面的莫队，那么离散化一下，莫队总长度应该是 $\mathcal O(n\log_{B+1}n)$ 的，$B=3$ 即可通过。

[Ynoi2013] 对数据结构的爱

先考虑能不能分块。我们希望能预处理每块 $B+1$ 段的分段函数，这样可以单次 $\mathcal O(B+\dfrac{n}{B}\log n)$ 内回答一个询问。考虑分治，令 $f_i,g_i$ 分别表示序列的 $[L,\text{mid}],(\text{mid},R]$，能减掉 $i$ 个 $p$ 的最小初始值。容易发现最终 $[l,r]$ 要减掉 $t$ 个 $p$，左区间减掉 $p$ 的个数越小越好，合并可以线性双指针。其实可以发现直接对整个序列分治，等价于线段树，复杂度是 $\mathcal O(n\log n +m\log^2 n)$，足以通过此题。

如果直接暴力分块，复杂度是 $\mathcal O(n\log n+m\sqrt{n\log n})$。预处理和查询不平衡，可以做两次分块（其实等价于两层的线段树，还是一样的），分别取块长为 $B$ 和 $\sqrt{nB}$，那么询问可以分成 $\sqrt{\dfrac{n}{B}}$ 个大小为 $\sqrt{nB}$ 和 $B$ 的块，还有 $\le4$ 块大小为 $B$ 的散块，复杂度为 $\mathcal O(B+\sqrt{\dfrac{n}{B}}\log n)$，平衡 $B=n^{\frac{1}{3}}\log^{\frac23}n$ 得到复杂度为 $\mathcal O(n\log n+mn^{\frac 1 3}\log^{\frac 2 3} n)$。

[Ynoi2012] 惊惶的 SCOI2016

对于每种颜色单独统计贡献，容斥一下变为求有色连通块平方和，每个点记录以其为根的有色连通块大小。修改需要查询一个点深度最大的无色祖先，这个可以树剖对每条重链维护一个 set；还需要求孩子的连通块平方和，动态维护每个点的轻儿子平方和，修改只要 $\log n$ 次，时间复杂度单 $\log$。

[Ynoi2002] Adaptive Hsearch&Lsearch

我们对平面按照网格长度为 $2^k$ 分块，每次只要找到每个块内相邻 $R$ 个点对和相邻块合并起来，按照编号排序相邻的 $R$ 个点对，其中 $R$ 是一个常数，取 $7$ 左右，大概的构造可以看一下讨论区的 hack，原理就是对于一个固定的 $k$，构造一个块内的 $7$ 个点，使得这 $7$ 个点在划分成 $2^{k-1}$ 的时候不在一个块。然后就是二维数点，因为支配对数量太大了所以分块平衡一下，时间复杂度 $\mathcal O(nR\log n\log V +q\sqrt n)$。

[Ynoi2004] rpmtdq

先把树点分了，那么两点距离变成了 $d(rt,u)+d(rt,v)$，不用考虑同个子树的问题，因为不优（好写一点）。$\mathcal O(n\log n)$ 个支配对，离线乱做。

[Ynoi2024] After god

换维扫描线，对序列扫，那么就是区间 chkmax 历史和，可以吉司机，然后历史和随便怎么写都行。当然此题也有比较繁琐的单侧递归线段树的 2log 做法，不赘述。

[Ynoi2009] pmrllcsrms

序列每长度为 $c$ 分一块，三种情况，整块内，跨整块，跨散块，都好算。

[Ynoi2009] rprmq1

把矩形第一维拆分掉，把询问第二维放到线段树上，直接对这个线段树 dfs，同时维护一个历史最大值线段树就对了，$\mathcal O(n\log ^2 n)$，把第二维换成二区间并可以砍掉一个 $\log$。

[Ynoi2008] rdCcot

[Ynoi2011] 成都七中