【施工中】Ynoi笔记
FunnyCreatress
·
2021-12-29 20:29:09
·
个人记录
退役了，断更。
因为无事可做所以整理一下之前写（或口胡）的毒瘤题（实际上是为了过一遍DS思想，之后稍微做点思维题所以碰DS可能少点），大致按难度排序。事实上难度可以通过题解长度大致看出来
事实上这里应该还有一篇数据结构总集但它咕了
复杂度中同阶的玩意不作区分。
给难度稍微做了个量化，分成思维和代码难度，各5分。由于个人体感问题，\le 2.5 的部分可能不准。
个人认为总分 \ge 6 的题算是比较有趣的。
[Ynoi2011] 初始化 （1+1）
题意：下标等差数列加，区间和。n,m\le 2\times 10^5 。
tag：根号分治，分块。
根号分治。对公差大于 \sqrt n 暴力，用 O(1)-O(\sqrt n) 分块维护。对公差小于 \sqrt n 的，对每个公差维护每个可能首项的修改总量的前缀和，查询枚举公差，随便算算就行。复杂度 O(n\sqrt n) 。
[Ynoi2013] 大学 （1+1.5）
题意：区间能被 x 整除的除以 x ，区间求和。强制在线。n,m\le10^5,a_i\le 5\times 10^5 。
tag：树状数组，并查集
先处理出每个因数对应的可能位置。每次遍历可能位置，除不动了就删掉，用并查集维护。显然序列变动最多 O(n\log A) 次，用树状数组维护。复杂度 O(nd(A)+n\log A\log n) ，d(A) 是 1-A 内最多因子数。
[Ynoi2016] 炸脖龙 I （1+1.5）
题意：区间加，区间幂塔取模。n,m\le 5\times 10^5,p\le 2\times 10^7 。
tag：扩展欧拉定理，树状数组
序列用树状数组维护，区间幂塔显然可以使用扩展欧拉定理在 O(\log^2 p) 内求出，注意判边界。复杂度 O(n\log^2 p+p) 。
[Ynoi2017] 由乃的OJ （1+2）
题意：给一棵树，每个节点代表和一个数做某种位运算，单点修改，查询选去不超过给定值的数，经过一条路径后最大可能值。n,m\le 10^5,V<2^{64} 。
tag：树剖，线段树
树剖。每个线段树节点维护全 0/1 权值正着/反着经过后变成什么，查询直接按位贪心。树剖可以换成 GBT。复杂度 O(n\log^2n) 或 O(n\log n) 。
[Ynoi2005] rpxleqxq （1+1.5）
题意：区间异或和 \le x 点对数。n,x\le 2\times10^5,q\le 10^6 。
tag：莫二离
莫二离板板。随便用个高低位分块就做完了。复杂度 O(n(\sqrt V+\sqrt m)) 。
[Ynoi2019] Yuno loves sqrt technology II （1+1.5）
题意：区间逆序对。n,m\le 10^5 。
tag：莫二离
莫二离板板。搞完随便拿个 O(\sqrt n)-O(1) 分块就行。复杂度 O(n\sqrt n) 。
[Ynoi2019] Yuno loves sqrt technology III （1+1.5）
题意：区间众数出现次数。强制在线。
tag：序列分块
分块。先求出整块间答案，查询时在此基础上扩展，每次最多使答案+1，检验一下新加入的数就行。复杂度 O(n\sqrt n) 。
[Ynoi2009] rprsvq （2+1）
题意：区间加，区间所有子序列方差和。n\le 5\times 10^6,m\le 10^5 。
tag：推柿，线段树
先推柿。发现查的东西是一个有关区间长度的常数乘上区间方差。常数手算个几项往OEIS上一扔发现有个 O(n) 的递推。区间方差线段树乱杀。复杂度 O(n+m\log n) 。
[Ynoi2017] 由乃的玉米田 （1.5+1.5）
题意：区间和差积商为给定值数对存在性。n,m,a_i\le 10^5 。
tag：莫队，bitset，根号分治
莫队。和差用bitset解决，积直接枚举因数，商用根号分治。大于 \sqrt V 部分直接枚举较小数，小于部分离线下来，求出每个前缀的可能答案中左边最靠右的一个，右端点对应前缀对应左端点在区间内即可。复杂度 O(n\sqrt n+\dfrac {n^2}w) 。
[Ynoi2012] NOIP2016 人生巅峰 （2.5+1）
题意：区间立方取模，区间和相等集合存在性。n,m\le 10^5,v\le 1000 。
tag：不明
区间长度较大（> 13 ）时根据抽屉原理必然有解。否则直接爆搜所有集合。区间立方随便打个tag查询时求值就完事了。复杂度 O(n(L\log n+2^L)) ，其中 L=13 ，跑不满所以快的一批。
思维2.5是给bitset优化DP的，不是给这玩意的。
[Ynoi2013] 无力回天 NOI2017 （1.5+2）
题意：区间xor给定值，区间求给定值与子集xor最大可能值。n,m\le 5\times 10^4,a_i,v\le 10^9 。
tag：线性基，线段树
查询显然用线性基。注意到序列线性基等价于xor差分序列的线性基，所以只要点修区间线性基，线段树即可。复杂度 O(n\log n\log^2V) ，线性基合并写的好的话常数很小，稳过（实际上瞎jb写也能过）。
[Ynoi2016] 这是我自己的发明 （1+2）
题意：给定带点权树，换根，两棵子树内点权相等点对数。n\le 10^5,m\le 5\times 10^5 。
tag：莫队
换根显然假假，拍成序列后直接差分询问，莫队即可。复杂度 O(n\sqrt m) 。
[Ynoi2016] 掉进兔子洞 （1+2）
题意：求三个区间的共同元素数。n,m\le 10^5 。
tag：莫队，bitset
先离散化，然后莫队套bitset即可。卡空间，所以要对询问分成3~4块做。复杂度 O(n\sqrt n+\dfrac {n^2}w) 。
[Ynoi2006] spxmcq （1+2.5）
题意：给定带点权有根树，查询子树假如加给定值后包含根的最大权连通块。n,m\le 10^6,|a_i|,|x|\le 10^8 。
tag：线段树合并
先考虑无修，发现是智障DP。离线询问，自底向上遍历整棵树，支持线段树合并和区间推平。复杂度 O(n\log A) 。
[Ynoi2010] Fusion tree （1.5+1.5）
题意：给定带点权树，邻居+1，单点减，邻居异或和。n,m\le 5\times 10^5,a_i\le 10^5 。
tag：01trie
对父亲的维护是平凡的，考虑对每个点维护其所有子节点从低位到高位的01trie。值+1相当于结尾1变0，就是把整颗trie的最右链换到最左链，顺手维护一下就行。复杂度 O(n\log n) 。
[Ynoi2005]tdnmo （2+1）
题意：不会简化，看原题去。
tag：Top Cluster
求出来 Top Cluster 的界点之后类似回滚莫队就行，操作数 O(n) ，总代价 O(n\sqrt n) 。
挺简单的，毕竟我都能在 THUPC Pre 考场上把这题日了然后把全场前三水的一个题漏了。
可能更详细的题解
[Ynoi2006] rldcot （2+2）
题意：给定带边权树，区间不同lca深度数。n\le 10^5,m\le 5\times 10^5 。
tag：LCT，某经典区间询问离线trick
按右端点离线询问，维护每种lca深度最后出现的位置。相当于每次对当前点做 access 操作顺带更新中途经过的链，LCT即可。复杂度 O(n\log^2n+m\log n) 。
[Ynoi2016] 谁的梦 （1.5+2）
题意：给定若干序列，单点修改，查询每个序列中取一子串后不同颜色种数和。n,m,\sum len_i\le 10^5 。
tag：STL
考虑每种颜色对答案的贡献。取反后转化为不包含的子段数，用set维护每种颜色出现位置即可。复杂度 O(n\log n) 然而我竟然卡了好久常数才过并跑到了最劣解。
[Ynoi2005] vti (1.5+2)
题意：虚树支配对数。n\le 10^5,m,\sum t_i\le 10^6 。
tag：莫二离
先把虚树容斥成若干条直系链上支配对数，然后把树拍成欧拉序跑莫二离就完事了。复杂度 O(n\sqrt{\sum t_i}) 。
我在10min内能胡出来的题大概也就是这个难度了。
可能更详细的题解
[Ynoi2007] rfplca （2.5+1.5）
题意：区间父亲编号减，两点 LCA，强制在线。n,m\le 4\times 10^5 。
tag：序列分块
分块。借用弹飞绵羊的思路，维护每个点第一次跳出块的位置，以及块内两点LCA是否在块内，用并查集。如果跳一次就出去了那么以后的更新就不管它。查询时先跳进对的块里，暴力跳就完事了。复杂度 O(n\sqrt n) 。
[Ynoi2008] rrusq （2.5+2）
题意：区间矩形并关键点权和。n,m\le 10^5,q\le 10^6 。
tag：某经典区间询问离线trick，KDT，分块
按右端点离线询问，将所有关键点建出KDT，给每个点记一个标记表示这个点最晚出现的矩形，那么转化为矩形标记推平，查标记 \ge l 的权值和。注意到推平这个东西均摊复杂度是 O(n\sqrt n) 的，因此直接拿个 O(1)-O(\sqrt n) 的分块维护就行。复杂度 O((n+q)\sqrt n) (事实上复杂度瓶颈还是KDT/qd)。
[Ynoi2008] stcm （2.5+1.5）
题意：给定树，要求构造一个方案，用插入、撤回操作标记每棵子树的补集。要求复杂度 O(n\log n) 。
tag：树剖，哈夫曼树
先考虑类似 dsu on tree 的做法，从上到下解决每一条重链。显然一条重链可以在 O(size) 的复杂度内解决，然后把挂在重链上的所有子树拉出来建哈夫曼树，然后dfs一遍就行。由于哈夫曼树的性质，复杂度是 O(n\log n) 的。
这种题还是有点意思的，可惜难度不大。
[Ynoi2015] 盼君勿忘 （3+1.5）
题意：区间所有子序列去重和取模。n,m,a_i\le 10^5 。
tag：莫队，根号分治，光速幂
考虑一种值 x 的贡献，显然为 x(2^{len}-2^{len-cnt_x}) 。先整体提出 2^{len} ，那么前面是区间去重和，容易解决。后面一部分对 x 出现次数做根号分治，出现多的处理光速幂快速统计，出现少的对每种不同出现次数统计 x 的和一起算。复杂度 O(n\sqrt n) 。
[Ynoi2018] 五彩斑斓的世界 （2+2.5）
题意：区间 >x 的数 -x ，区间元素出现次数。n\le 10^6,m\le5\times 10^5,a_i\le 10^5+5,7.5s 。
tag：序列分块
分块。拿个并查集维护块内值出现位置。散块直接暴力重构，整块对最大值分类讨论，\le 2x 时暴力减，否则把不超过 x 的加上 x ，然后打上整体减的tag。这样块内并查集合并次数是 O(V) 的。卡空间，离线后每块分别维护，复杂度 O((m+V)\sqrt n) 。
[Ynoi2018] 未来日记 （2.5+2.5）
题意：区间 x 变 y ，区间 k 小，n,m,a_i\le 10^5 。
tag：序列分块，值域分块
分块。维护每个块前缀块内的块状权值数组并同时拿个并查集存出现位置。查询时先找到在哪个权值块，再逐个去找答案。复杂度 O(n\sqrt n) 。写的时候因为没判 x,y 相等挂了亿发，属于傻逼是了。
[Ynoi2019] Yuno loves sqrt technology I （2+2.5）
题意：区间逆序对。强制在线。n,m\le 10^5 。
tag：序列分块。
分块，预处理出每个点到每个整块点的答案，并且每块块内排序一下，查询时只需要额外归并两边就行，单块内部处理类似。复杂度 O(n\sqrt n) 。
[Ynoi2008] rsmemq （3+2）
题意：区间中点下标为区间众数的子区间数。n,m\le 5\times 10^5 。
tag：根号分治
显然有每个点向外延伸的合法段数总和不超过 O(n) 。根号分治，出现次数多的暴力，次数少的算出每种众数出现次数的极长区间，二分求解。查询是平凡的，线段树即可。复杂度 O(n\sqrt n) 。
[Ynoi2015] 世上最幸福的女孩 （2+3.5）
题意：全局加区间最大子段和。n\le 3\times 10^5,m\le 6\times 10^5 。
tag：线段树，闵可夫斯基和
知道闵可夫斯基和那这题就是个无脑题。然而由于时空问题，询问需要离线下来然后用指针扫凸包，还要通过一些手段把空间搞成线性。复杂度 O(m\log n) 。
专讲卡空间方法的题解
[Ynoi2011] WBLT （3+2）
题意：区间最长首项 <b ，公差 =b 等差集大小。n,m,a_i\le 10^5 。
tag：莫队，bitset，不明分治
莫队，对 b\ge w 的询问维护区间出现的数的bitset，直接大力算，对 b<w 的询问每种 b 分开做，每个 b 维护 \bmod\ b 的每个剩余类的bitset，这部分复杂度由均值不等式可知为 O(n\sqrt {nw}) 。bitset需要手写。复杂度 O(n\sqrt {nw}+\dfrac {n^2}w) 。
[Ynoi2018] 天降之物 （3+2）
题意：序列所有 x 变 y ，值为 x 和 y 的最小距离。n,m,a_i\le 10^5 。
tag：根号分治
先考虑无修，对出现次数根号分治，出现次数多的预处理与其他数的距离，出现次数少的查询时归并。加入修改操作后，对每种值引入一个附加集合，表示是这个值但暂时没有并入的位置。修改时分别合并位置集合和附加集合，若附加集合大小 >\sqrt n 就重构。查询时查位置集合，归并附加集合。复杂度 O(n\sqrt n) 。
关于此题的序列分块版本，有空再研究下。
[Ynoi2013] 对数据结构的爱 （3.5+1.5）
题意：区间伪取模和。n\le 10^6,m\le 2\times 10^5 。
tag：线段树
一个经典套路，没什么规律且依次执行的区间询问可以用线段树维护分段函数解决。本题中有结论，长为 len 的区间是至多 len 段的分段一次函数，具体结论可参考题解。查询时每次lower_bound一下就行。复杂度 O(n\log n+m\log^2 n) 。
[Ynoi2009] rla1rmdq （2.5+2.5）
题意：给定有根有边权树，区间跳父亲，区间最小深度。n,m\le 2\times 10^5 。
tag：序列分块
分块。观察到若一个块内两点为祖先关系，那么查整块时较深的那个点就没用了，以后更新中不管它。重构可能导致死掉的点复活，但不是大问题。复杂度 O(n\sqrt n) 。
[Ynoi2006] rmpq （3.5+2）
题意：半平面乘，单点查，乘法不满足交换律。n\le 10^5 ，乘法次数不超过 O(n\sqrt n) 。
tag：操作分块，分治
对操作分块，每块将平面分成 B\times B 个部分，直接求复杂度爆炸，因此分治，每层合并前一半操作和后一半操作，复杂度是正确的。查询时可能需要二分多个 \log ，但这不重要，能过。二分之外复杂度为 O(n\sqrt n) 。
**[[Ynoi2013] D2T2](https://www.luogu.com.cn/problem/P5611)**（3+2.5）
题意：区间保留值域区间最大子段和。$n,m\le 10^5$。
tag：分块，分治
显然有一个智障的 $O(n\sqrt n\log n)$ 莫队做法，然而这个做法并没有吊用。对原序列分块，我们试图在 $O(n)$ 内处理出每个块的每个值域区间的子段和信息。用上一道题那个神奇的分治即可。复杂度 $O(n\sqrt n)$。巨大卡常，不要写 vector，写个静态内存池用指针可以卡一些常数。
**[[Ynoi2008] rdCcot](https://www.luogu.com.cn/problem/P7126)**（3.5+2.5）
题意：给定树，距离 $\le C$ 的点对连边，区间导出子图连通块个数。$n\le 3\times 10^5,m\le 6\times 10^5$。
tag：点分治，平衡树
考虑对每个连通块寻找一个代表元，取其中以深度为第一关键字，编号为第二关键字中最小的一个。设 $l_i,r_i$ 分别为 $<i$ 和 $>i$ 的节点中最近的距离 $\le C$ 且序比 $i$ 小的点，使用点分治+平衡树求出。剩余问题是个简单的二维数点。复杂度 $O(n\log^2n+m\log n)$。有点卡常= =。
**[[Ynoi2018] GOSICK](https://www.luogu.com.cn/problem/P5398)**（3.5+2.5）
题意：区间值成倍数关系点对数。$n,m,a_i\le 5\times 10^5$。
tag：莫二离，根号分治
先上莫二离。问题转化为 $O(\sqrt n)$ 加入一个值，$O(1)$ 查询当前有几个值是给定值的因数或倍数。$O(\sqrt n)-O(1)$ 查倍数是容易的。查因数需要根号分治。大的直接暴力给所有倍数加一，小的分开做，对每一种的前缀求出有几个数是其倍数。由于莫二离变化区间总数为 $O(n)$，所以可以用前缀和 $O(1)$ 查。复杂度 $O(n\sqrt n)$，然而实际测出来由于不明原因根号分治阈值要取到 $50$~$60$。
**[[Ynoi2016] 镜中的昆虫](https://www.luogu.com.cn/problem/P4690)**（2.5+3）
题意：区间推平，区间数颜色。$1\le n,m\le 10^5$。
tag：STL，cdq分治
~~相比其他几道口胡题真的算是小清新了，有空补掉。~~ 已切
注意到区间数颜色有个经典套路，就是只算最先出现的那个。考虑维护序列的 pre 数组，查询是一个二维数点，~~树套树就行~~ 被 lxl 卡了空间，现在要离线后 cdq 分治。修改的时候由于颜色段均摊的一些理论，pre数组变化次数仅为 $O(n+m)$，问题变为快速找到变化的位置，这玩意拿个 set 维护就行。可能有一定细节。复杂度 $O(n\log^2n)$。
**[[Ynoi2077] stdmxeypz](https://www.luogu.com.cn/problem/P7710)**（2.5+3）
题意：给定树，子树内深度膜 $x$ 余 $y$ 的点加，点查。$n,m\le 3\times 10^5$。
tag：根号分治，分块，长链剖分
根号分治。$x>\sqrt n$ 时只会加不超过 $\sqrt n$ 层，每层在 bfs 序上是连续的，用 $O(1)-O(\sqrt n)$ 分块维护。$x\le \sqrt n$ 时对每种 $x$ 分开搞，这次把点按深度膜 $x$ 为第一关键字，dfs 序为第二关键字重新编号，每次更新是一个区间，用 $O(\sqrt n)-O(1)$ 分块维护。但是定位区间如果暴力二分会多半个 $\log$，如果放在序列上我只会 Fractional Cascading，常数很大而且写起来很不友好。然而这是树，我们要知道一个子树内深度为 $x$ 的最大/小 bfs 序，显然是个长剖。直接写是 $O(n\sqrt n)$ 空间的，不太能过。我们可以时间换空间，每次长剖只处理 $O(\sqrt n)$ 个修改，这样空间降为 $O(n)$，时间复杂度仍为 $O(n\sqrt n)$，就是常数变大了点。
**[[Ynoi2007]rcn](https://www.luogu.com.cn/problem/P7721)**（3+3）
题意：矩形数颜色，带权。$n\le 10^5,m\le 10^6$。
tag：回滚莫队 (无增)，二维分块
先莫队掉一维，然后用经典区间数颜色trick转化为二维分块。由于要动态 $O(1)$ 求前驱后继所以要用无增回滚。
还是很好想的。~~除非你和我一样被无增回滚杀两次（上一次是秃子酋长）~~
**[[Ynoi2008] rplexq](https://www.luogu.com.cn/problem/P6782)**（3+3）
题意：给定有根树，区间LCA等于 $x$ 点对数。$n,m\le 2\times10^5$。
tag：莫队，根号分治，分块
先将等于 $x$ 转化为在 $x$ 子树内且不在 $x$ 儿子的子树内。莫队，对子树大小根号分治，$x$ 子树大小 $<\sqrt n$ 直接暴力算，否则对儿子子树大小根号分治，大子树用一个假的二次离线，在 dfs 序上 $O(\sqrt n)-O(1)$ 维护子树内点数，小子树正常莫队时一起算就行。复杂度 $O(n\sqrt n)$。
**[[Ynoi2006] rsrams](https://www.luogu.com.cn/problem/P7882)**（3+3.5）
题意：区间绝对众数和。$n,m\le 10^6,8s$。
tag：莫队，根号分治，分块
根号分治。多的对每种颜色分开考虑，保留有效点后调节块长莫队，少的统一拉出来二维数点，$O(1)-O(\sqrt n)$ 分块维护。复杂度 $O(n\sqrt n)$。
可能稍微详细点的[题解](https://www.luogu.com.cn/blog/HailToTheFunnyGod/solution-p7882)
**[[Ynoi2011] 成都七中](https://www.luogu.com.cn/problem/P5311)**（3.5+3）
题意：给定树，点有颜色，保留区间后包含 $x$ 的连通块颜色数。$n,m\le 10^5$。
tag：点分树，树状数组
分两步走，定位连通块和查颜色数。对原树建点分树，把要的连通块挂在点分树中最浅的那个点上，这容易单次 $O(\log n)$ 做到。然后在点分树上求解，发现是一个二维数颜色问题，按照套路离线下来后维护每种颜色最后出现的位置，复杂度 $O(n\log^2n)$。
连通块相关DS题似乎很多都可以点分树解决，吗
码量其实不大，但给了3是因为个人写淀粉质相关DS时不太顺手。
**[[Ynoi2009] rprmq1](https://www.luogu.com.cn/problem/P6109)**（3.5+3.5）
题意：矩形加后矩形最大值。$n,m\le 5\times 10^4,q\le 5\times 10^5$。
tag：二区间合并，线段树（历史最值）
考虑在线化，将其中一维作为时间轴，在这维上分治，将询问拆成左右两段，转化为区间历史最值问题，线段树即可。复杂度 $O(n\log^2n+q\log n)$。
**[[Ynoi2006]rprmq2](https://www.luogu.com.cn/problem/P7899)**（3+4）
题意：矩形加，矩形查max (有所改动但不影响做法)。$n,m\le 2\times 10^5$。
tag：根号重构，KDT，线段树 (历史最值)。
会 rprmq1 的话你大概能在 30min 内想出此题的 $O(n\sqrt n\log n)$ 做法。
我们每次处理 $B$ 个操作，这 $B$ 个操作将矩阵划成了至多 $B\times B$ 个矩形，显然我们只关心每个矩形中的最值。离线前面的操作，用历史最值线段树维护信息，得到每块的初始值。块内在 KDT 上暴力修改、查询就行。此处 KDT 可以用所谓的“四分树”实现，这样就简单地做到了 $O(n\sqrt n\log n)$。这时候我们微调历史最值线段树的形态，先把每个块当成整体建树，然后块内再建树。通过根号平衡可以做到 $O(n\sqrt{n\log n})$。
常数超了至少 $4$ 倍，弃了。
**[[Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？](https://www.luogu.com.cn/problem/P4118)**（2.5+4.5）
题意：区间加区间最大子段和。$n,m\le 10^5$。
tag：序列分块，线段树，闵可夫斯基和
分块。散块利用线段树 $O(\sqrt n)$ 重构，整块离线所有询问后指针扫一遍。复杂度 $O(n\sqrt n)$，除了码量巨大感觉没什么技术含量？
**[[Ynoi2007] rgxsxrs](https://www.luogu.com.cn/problem/P7447)**（4+3.5）
题意：区间大于 $x$ 的减 $x$，区间最值/求和，强制在线。$n,m\le 5\times 10^5,a_i\le 10^9$。
tag：倍增分块，线段树（with底层分块优化空间）
真的思博题。设一个底数 $B$，将值为 $[B^i,B^{i+1})$ 的数分在同一层内，每层维护一棵线段树，每次更新时，不发生层间变化的部分用tag解决，层间变化暴力处理。复杂度由几个部分构成。
1.“跌落”部分：每个值至多跌落 $\log_BA$ 层，每次修改 $O(\log n)$，复杂度 $O(n\log n\log_BA)$。
2.tag部分：每次修改仅有一层内同时有减了 $x$ 和不减 $x$ 的数，但层内最多减 $B$ 次就会发生跌落，复杂度 $O(nB\log n\log_BA)$，其他层正常打tag显然不影响复杂度。
因此复杂度为 $O(nB\log_n\log_BA)$，$B$ 不瞎jb取就行。
为什么能优化？因为充分发扬了线段树的优良tag传统。
**[[Ynoi2009] rpdq](https://www.luogu.com.cn/problem/P6778)**（不会 Top Cluster 3.5+4，会 Top Cluster 3+3）
题意：给定带边权树，区间点对距离和。$n,m\le 2\times 10^5$。
tag：莫二离，(根号分治，分块)/Top Cluster
sol1 (没点 Top Cluster 科技，原始做法)：先莫二离，转化问题为 $O(\sqrt n)$ 加点，$O(1)$ 查单点到已加入点的距离和。对子树大小根号分治，小于根号的子树暴力 BFS 更新。剩下点拉出来建虚树，BFS 更新的同时更新所在虚边信息，在dfs序上分块维护相当多的信息。复杂度 $O(n\sqrt n)$ 且写的不好需要巨大多卡常。
sol2 (科技)：sol1 的基础上把后面根号分治一系列东西换成 Top Cluster，可以轻松维护。
科技改变命运。但不会科技也问题不大。
可能更详细的[题解](https://www.luogu.com.cn/blog/HailToTheFunnyGod/solution-p6778)
**[[Ynoi2007] rdiq](https://www.luogu.com.cn/problem/P7448)**（3.5+4）
题意：区间本质不同逆序对数。$n\le 10^5,m\le 5\times 10^5$。
tag：莫二离，二维分块
考虑对每个本质不同的逆序对取一个代表，不难想到这个代表是较大数最靠前者和较小数的最靠后者。将左端增量和右端增量分开来求。使用莫二离，不妨仅考虑左端点左移的增量，显然为新左端点右下的点数减去新左端点后继右下角点数。用一个 $\big(O(n^{0.25})-O(1)\big)^2$ 的二维分块维护。然而直接实现常数过于巨大。注意到同一时刻每行每列至多一个点，所以我们仅维护块长 $O(\sqrt n)$ 以上的部分，剩余部分可以反过来计算每个点对每个查询位置的贡献。复杂度 $O(n\sqrt m)$。莫二离和常规莫二离不太一样，要注意下。
**[[Ynoi2077] 3dmq](https://www.luogu.com.cn/problem/P7711)**（3.5+4.5）
题意：三维偏序加，三维偏序点权和。$m\le 10^5,n,q\le 5\times 10^5,30s$。
tag：根号重构，二维分块
先整两种暴力，一种纯暴力，一种算修改对询问贡献的暴力，根号重构摊平，转化为修改和询问量不对等的三维偏序，二维分块解决。复杂度 $O(n\sqrt n)$，巨大卡常，T了两秒/tuu，可能会考虑加指令集。
代码贼寄八难写，成功打破Ynoi最长纪录。
可能更详细的[题解](https://www.luogu.com.cn/blog/HailToTheFunnyGod/solution-p7711)
**[[CTS2022] WBTT](https://www.luogu.com.cn/problem/P8262)**（4/4.5+5）
题意：维护树，支持换父亲，用自己造出来的集合表示链，合并集合代价为大小之和，要求单次代价 $O(\sqrt n)$。$n,m\le 10^5,10s$。
tag：喵喵树据结构，块状链表，根号分治，树剖
由于~~青蛙~~的提议将此题视为Ynoi。~~然后这个题有个奇怪的用处是把P4118上动态树~~
草了，竟然是另解
首先考虑这个题的链版本然后随便嘴巴出一个 $O(n\sqrt {n\log n})$ 的块链暴力然后会发现它是一个暴力。
然后发现这半个 $\log$ 去不掉然后开始手玩标题，然后玩出来了一个支持线性合并/分裂的妙妙平衡三叉树，然后就能把那两个特殊性质点切掉了。
然后你要上树，首先会想到 Top Cluster 但还要动态化实在太烦了。于是就对子树大小根号分治，子树大的节点形成一个虚树状物，拿之前链部分的做法维护，子树小的节点就分开维护。然后发现需要一个把链换到虚树上的操作所以需要额外维护小子树的重链信息。
然后只要实现一个400行的东西外加一堆部分分的gen和checker就好了。
思维难度存疑，~~因为我是通过破解标题才想到这个东西的，凭空想到的难度应该会更大~~ 后来证明破解标题是个意外。其实感觉就算直接把这个东西给出来后面的内容也有3.5~4分了。
可能更详细的[题解](https://www.luogu.com.cn/blog/HailToTheFunnyGod/solutoin-p8262)
~~那个solutoin是因为本来那个题解交错题了~~
---
以下是口胡部分
---
**[[Ynoi2019] Happy Sugar Life/[NOI2020]时代的眼泪 卡时空版](https://www.luogu.com.cn/problem/P6579)**（4+4.5）
题意：矩形支配对数。$n,m\le 10^5$。
tag：二维分块
~~duliu~~。似乎std是树套树分治，然而我对树分治理解过于不透彻所以不会。考虑二维分块，将平面划成 $\sqrt n\times \sqrt n$ 个部分，不妨考虑矩形长宽均超过 $\sqrt n$ 的情况，此时矩形被网格分为九个部分，分别考虑块内和块间贡献，大力讨论七类情况后发现是可以做的，离线询问后可做到线性空间。
有亿些恶心，毕竟在线版都有8kb码量(虽然很多可以复制粘贴)，而且卡常可能还得费点功夫。但代码难度不给5是因为只要思路对了外加手稳写起来手感不错。
可能更详细的[题解](https://www.luogu.com.cn/blog/HailToTheFunnyGod/solution-p6774)（虽然只是不卡时空版的）
**[[Ynoi2019] 美好的每一天~ 不连续的存在](https://www.luogu.com.cn/problem/P6580)**（~~4.5+5？~~ 4?+3.5?）
题意：给定树，点有颜色，每次询问保留区间内点后每个连通块内出现次数为奇数的颜色数对应贡献之和。$n,m\le 10^5,x\le 10^4$。
tag：莫队×2，线段树合并，点分树
一个nb题。在这题之前您可能需要解决[这题](https://www.luogu.com.cn/problem/P5311)。
先回滚莫队。先不管左边的零散点，右端点每次右移时合并颜色的线段树并统计答案。然后考虑零散点。直接暴力显然复杂度是错的，考虑单独计算，用上面那题的思路，把每个零散点的询问挂到点分树上，统一计算答案。然后还需要减掉零散点相邻连通块的贡献。这部分可以在合并联通块时解决，将每个连通块的贡献归到与之相邻的编号最大的零散点上，这样可以保证不重不漏。点分树上的询问可转化为二维数奇数颜色数，这个可以直接莫队，但由于会有坐标相同的情况所以需要离散化一下，不过相比之前的东西是小问题。
线并部分复杂度显然是 $O(n\sqrt n\log n)$，点分树上由于每次询问的连通块互不相交，因此不会出现在同一棵点分树上，也就是说一棵点分树上的询问数不超过 $O(n)$，因此莫队的复杂度是 $O(n\sqrt n\log n)$。总复杂度也是 $O(n\sqrt n\log n)$~~，达到了lxl说的理论复杂度~~。
有很多细节没说，因为太难了所以不敢写，等哪次有个一星期时间可能可以肝。
lxl给这题的分数是 [6,10]，个人感觉以我的做法是可以取到10的。不排除更容易的做法。~~看除了lxl以外过的人的码长感觉到了亿丝不对劲~~
**[[Ynoi2013] Ynoi](https://www.luogu.com.cn/problem/P5612)**（3.5+5？）
题意：区间xor，区间sort，区间xor和。$n,m\le 10^5$。
tag：01trie分裂/合并，序列平衡树
众所周知sort完一个区间就排好序了（？废话）。考虑将序列分成若干个sorted段xor上一个值的形式。由于颜色段均摊之类的玩意，总共出现的sorted段数不超过 $O(n+m)$，那么我们拿个序列平衡树维护sorted段，有操作的时候把切到的段split一下，区间xor就在序列平衡树上打tag，区间sort就把有关段全部merge起来，查询直接查就行。复杂度 $O(n\log V)$。
个人感觉这个序列平衡树可能用WBLT会相当可，有待验证。但貌似不管怎么写都会导致码量极度巨大的结果，所以不管了。
**[[Ynoi2012] WC2016充满了失望](https://www.luogu.com.cn/problem/P5525)**（2.5+4.5）
题意：给定凸包，每次查询圆是否被凸包包含 (经过了一些trivial的转化)。$n,m\le 5\times10^5$。
tag：计算几何，平衡树
个人感觉这个题还是比较naive的~~毕竟一年前的我都会口胡~~
先随手判一发圆心是否在凸包内。然后就只要判定与圆心距离最近的边是否在圆外就行。我们类似voronoi图找出每条边的管辖范围，这个显然就是把角平分线拉出来，碰到了就合并，这部分用堆即可解决。把分界线搞出来后离线询问，从左到右扫描，维护个平衡树就行。复杂度 $O(n\log n)$。貌似很难写的样子。
**[[Ynoi2012] 惊惶的 SCOI2016](https://www.luogu.com.cn/problem/P5526)**（3+3.5）
题意：给定树，点有颜色，点修，树上所有有向路径颜色数和。$n,m\le 4\times 10^5$。
tag：LCT
正难则反，考虑计算每种颜色在几条有向路径中没有出现。显然是删去这种颜色的点各连通块的大小之和。考虑计算每次操作的增量，离线，每种颜色分别计算，连通块的贡献算在连通块中最靠上点的父亲头上，LCT维护就行。复杂度 $O(n\log n)$。
**[[Ynoi2018] 駄作](https://www.luogu.com.cn/problem/P5399)**（3+5？）
题意：给定树，求树上两圆中点对的距离和。$n,m\le 10^5$。
tag：树分块 (Top Cluster)
据说没有Top Cluster也能做，但有了就直接是板板了。Top Cluster 分块，块内点到端点距离和算算，以两端点为圆心的圆到端点距离和算算，查询时圆心所在块暴力算算，各块内贡献算算，块间树形DP算算，就结束了。复杂度 $O(n\sqrt n)$。
然后就被巩布的代码锤爆了。