ds。
oMin0
·
·
个人记录
口胡选手。
1. P4689 [Ynoi2016] 这是我自己的发明
双子树莫队。要维护两棵树内/外的贡献，再多四倍常数，可能过不去。
可以拆开跑四次，常数变成两倍。
题解全都不写双子树莫队？
2. P4690 [Ynoi2016] 镜中的昆虫
连续段均摊。单点修只需考虑前驱后继，BIT 套权值线段树，巨大常数 2\log。
3. P4117 [Ynoi2018] 五彩斑斓的世界
整块维护值域 merge。总变化量 O(V\sqrt n)。
卡空间。但是可以逐块处理。
4. P4692 [Ynoi2016] 谁的梦
最弱智的 Ynoi。
答案是每种数贡献加起来。单点修用 set 查前驱后继。维护 0 的数量避免除以 0。
5. P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I
复习区间逆序对。
分块。整块预处理区间逆序对。散块内部预处理前后缀逆序对。散对散归并。散对整预处理后查 \sqrt n 次 rk。
6. P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II
莫队二次离线。
指针 r\gets r' 贡献为 \sum\limits_{i=r+1}^{r'}\sum\limits_{j=l}^r [a_j>a_i]，差分下来 O(\sqrt n)-O(1) 单点加前缀查。
7. P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III
区间众数。使用 goodier 分块。
8. P5063 [Ynoi2014] 置身天上之森
线段树区间加是对每层做 单点加/区间打tag。
打 tag 做不了。但是可以按照节点长度分 2\log 组。分别做散块归并/整块打 tag 的区间加区间查 rk。
复杂度 O(\sum 2^i\sqrt {i2^i})=O(n\sqrt {n\log n})。
8. P5064 [Ynoi2014] 等这场战争结束之后
离线建操作树。加边撤销查 k 小。
点权离散化，对连通块值域分块。
值域整块不带 log（并查集预处理一遍。），散块要查 B 次所属连通块，可撤销并查集 B\log n，总时间复杂度 O(n\sqrt {n\log n})。
分块部分空间爆了。但是又可以逐块处理，空间线性，爆杀大部分题解。
9. P5065 [Ynoi2014] 不归之人与望眼欲穿的人们
一眼 CF1936D。
线段树启动。节点维护前后缀（\log V 个不同 OR）及其 merge 的信息。总信息量 n \log ^2 V。
单点修时改变 \log n\log V 个前后缀，前后缀 merge 总共要修改 \log n\log ^2 V 个答案。全局开值域线段树维护后缀 min，底层需要 set 处理每种值对应的答案，总复杂度 O(q \log^2 n\log ^2 V)。
查询单 log。
10. P5066 [Ynoi2014] 人人本着正义之名
goodier 教我可以维护极长 0/1 连续段。操作是区间推平&区间 0/1 段向左/右增长/缩短 一个单位，均摊 1\log。
11. P5068 [Ynoi2015] 我回来了
只有加入，还是全局查。利用单调性，对调和级数个区间处理其中第一个数的出现时间即可。\text{polylog}。
12. P5069 [Ynoi2015] 纵使日薄西山
按极值点分段。每段非极小值的位置按照下标奇偶性判断求和，极小值位置特判。平衡树维护，1\log。
题解怎么都在 ddp。/se
13. P5071 [Ynoi2015] 此时此刻的光辉
莫队 n\sqrt mw(V)。考虑找出前 B 小的质因数预处理。平衡到 nB+n\sqrt m\log V/\log (B\log B)，取 B=O(\sqrt m) 即可。
14. P5072 [Ynoi2015] 盼君勿忘
一次询问答案是 \sum i(2^{len}-2^{len-cnt_i})。莫队加根分即可。需要对每个 p 进行 O(\sqrt n)-O(1) 处理光速幂。
15. P5311 [Ynoi2011] 成都七中
传世经典。大小根 kruskal 重构树。子树交跑双子树莫队。
其实可以 \text{polylog}，离线下来，一棵树启发式合并另插到一棵树上链加单点查。找链可以 set 维护每种颜色虚树。
16. P5070 [Ynoi2015] 即便看不到未来
暴力扫描线。只关心 [a_i-11,a_i+11] 的上一次出现位置。分成常数段树状数组区间加。
17. P5309 [Ynoi2011] 初始化
对下标 \bmod x=y 的位置加 z。一眼根分，x 大枚举 kx+y 做 O(1)-O(\sqrt n) 单点加区间查；x 小时只需求 \sum[x=i][y\leq j]z，暴力就可以做到 O(x)-O(1)。
18. P5313 [Ynoi2011] WBLT
显然可以莫队 bitset 做到 O(n\sqrt m+nm/\min(w,b))。
题解有点抽象？谁家 $\sum n\sqrt {cnt_i}=n\sqrt {\sum cnt_i}$？$w$ 次莫队做法的题解复杂度要么没算要么算错了，怎么会是呢。
**19. P5314 [Ynoi2011] ODT**
邻域信息维护儿子。重剖，对轻儿子点权开平衡树，本身/父亲/重儿子暴力，复杂度 $2\log$。维护 $\log n/\log \log n$ 个重儿子可以在复杂度上除个 $\log \log$。
**20. P5354 [Ynoi2017] 由乃的 OJ**
树剖套线段树。维护必是 0/1 的位以及其他位与 $v$ 的对应关系。然后贪心。$O(n\log^2 n+nk)$。
**21. P5355 [Ynoi2017] 由乃的玉米田**
乘积可以对 $a_i$ 根分。商可以对 $x$ 根分。和/差可以莫队+bitset。根号加上 $na/w$。
**22. P5356 [Ynoi2017] 由乃打扑克**
goodier 秒了。按 $B$ 分块。散块归并。整块二分。$B=\sqrt n\log n$，时间 $O(n\sqrt n\log n)$。
**23. P5397 [Ynoi2018] 天降之物**
动态根分。每种颜色是若干小颜色和若干大颜色的并。颜色数量或 $size$ 大于 $B$ 时重构。大对其他可以预处理/小对小暴力，查询复杂度是大颜色数量乘上总颜色数量+小颜色 $size$，$O(nB^2+n^2/B)$，$B=n^{1/3}$，$O(n^{5/3})$。
发现大颜色合并也可以直接重构。于是取 $B=\sqrt n$，复杂度 $O(nB+n^2/B)=O(n\sqrt n)$。
感觉比题解的分块/goodier 的抽屉原理简单。
**24. P5398 [Ynoi2018] GOSICK**
听说过是二次离线莫队板子。
右端点 $r\gets r'$ 贡献是 $\sum\limits_{i=r+1}^{r'}\sum\limits_{j=l}^{i-1} ([a_i\mid a_j]+[a_j\mid a_i])$。
二次离线。差分。需要 $\sum\limits_{i=1}^{l-1}\sum\limits_{j=r+1}^{r'}([a_i\mid a_j]+[a_j\mid a_i])$。扫描线， $[a_j\mid a_i]$ 直接暴力；$[a_i\mid a_j]$ 需要对 $a_i$ 根分，$a_i>\sqrt V$ 直接暴力，否则枚举 $a_i$ 的值预处理。
时间 $O(n\sqrt m+n\sqrt V)$。
**25. P5524 [Ynoi2012] NOIP2015 充满了希望**
显然每次 3 操作只有两种可能的答案。一种是 $0$，另一种是执行全部操作时的答案。分界点可以区间覆盖成时间戳预处理一遍。查询是简单二维数点。
**26. P5525 [Ynoi2012] WC2016 充满了失望**
？
**27. P5526 [Ynoi2012] 惊惶的 SCOI2016**
听说正解是 LCT。但我只会大常数 $2\log$ 暴力。
先容斥，那只需求不包含每种颜色的路径数量。
离线点分，对分治子树内出现过的颜色分别开线段树，扫描线，dfn 区间 $+1/-1$，全局数最小值个数，显然是 $O((\sum size+m\log n)\log n)=O((n+m)\log^2 n)$。
感觉过不了。LCT/Top tree 还是太城市化了。
**28. P5527 [Ynoi2012] NOIP2016 人生巅峰**
简单题。区间长度 $\geq B$ 时一定有解，否则暴力。我很好奇 $B$ 具体是多少。
用朴素方法可以分析到 $14$，但这个界太宽泛了。
有题解猜测是 $\lceil\log_2v\rceil=10$，被我叉了。
当构造题做。打表猜到一种贪心，跑出来 $\max a_i=594, len=11$ 的无解情况。
上 oeis 查了半天，我猜的结论是对的。精确阈值是 $B=12$。
**29. P5529 [Ynoi2012] 梦断 SCOI2017**
？
**30. P5607 [Ynoi2013] 无力回天 NOI2017**
线段树维护线性基板子。异或差分变成单点修。$3\log$。
**31. P5608 [Ynoi2013] 文化课**
远古题单题。线段树维护连乘段，每个节点只有 $O(\sqrt {len})$ 种长度，区间赋值时暴力快速幂复杂度即为单根号。
**32. P5609 [Ynoi2013] 对数据结构的爱**
远古口胡题。离线扫描线，需要支持插入和值域区间加操作，使用值域有交 fhq 合并，可以势能分析证出 $2\log $ 的复杂度。
此做法常数大但可扩展性很强。
**33. P5610 [Ynoi2013] 大学**
维护倍数集合（即找每个数的因数）。由于因数变化单调，可以并查集维护（反正我在口胡，不妨假设自己会用 $O(1)$ 压位并查集）。每次 $O(\log+Δ)$ 找要修改的数，总修改次数 $O(n\log A)$，时间 $O(nd(A)+n\log A\log n)$。
**34. P5073 [Ynoi2015] 世上最幸福的女孩**
朴素分治是 $ans_{l,r}=\max\{ans_{l,mid},ans_{mid+1,r},rmax_{l,mid}+lmax_{mid+1,r}\}$。同理可以闵可夫斯基和再取 max 求 $(sum,len)$ 的 凸包，用线段树结构存，总点数线性对数。
询问离线到各节点扫一遍，时空复杂度 $O((n+m)\log n)$。
空间炸了，但求凸包也可以离线，在线段树上 dfs，每次用完就释放掉，空间 $O(n)$。
**35. P5611 [Ynoi2013] D2T2P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？**
没活不要硬整。
分块。线段树预处理凸包。修改时散块线段树暴力 pushup；查询时散块暴力，整块分别按照 pushup 的关键时刻分段离线扫凸包。以上三部分复杂度是 $O(\sum B/2^i)=O(B)$，$O(B)$，$O(mn/B+mB)$。合起来单根号。
**36. P5611 [Ynoi2013] D2T2**
学习新 trick。
每个下标区间的本质不同值域区间只有 $O(len^2)$ 个。所以对每块离散化即可平衡到 $O(n\sqrt n)$。！！
细节上：查询显然可以离线下来逐块双指针；预处理时需要非常 nb 的分治，双指针合并，复杂度 $T(len)=2T(len/2)+len^2=O(len^2)$。
**37. P5612 [Ynoi2013] Ynoi**
区间排序一般可以类似 P2824 地连续段均摊，然后内外分别维护。
内层直接 01trie。区间异或时打 tag，排序时按 tag swap 儿子，分裂合并直接暴力，复杂度与线段树分裂合并一致；外层直接线段树维护整段异或和。总共 $1\log $。
我全对了。
**38. P6018 [Ynoi2010] Fusion tree**
同 P5314 地维护儿子。那么需要全局加一/单点修/求全局异或和。使用经典 01trie 套路 swap 儿子即可。$1\log $。
**39. P6019 [Ynoi2010] Brodal queue**
需要求区间 $\sum cnt_i^2$。
试图对块的区间维护答案，散块暴力加入。全错了。
题解第一步就没想到。差分后需要维护前缀 $\sum cnt_i^2$ 和每两个前缀 $cnt_i$ 的乘积之和。
然后再颜色段均摊。修改时只关心散块中颜色段的贡献，纯色块在查询时可利用区间 $cnt$ 信息暴力算。
**40. P6020 [Ynoi2010] Exponential tree**
远古讲课题。这不是我们 CTT2021。
大概做法是。迭代。
$k=1$ 时构成基本结构，$j>i$ 全填 $1$。
$k=2$ 时构成另一个基本结构，猫树分治。
$k>2$ 时考虑扩展这两种结构。分块，每块处理前缀后缀信息，块内递归，块间使用 $k-2$ 级做法维护。据说可以找精细分界点冲过去。
**41. P6105 [Ynoi2010] y-fast trie**
简单题。只需要考虑使得 $(x+y)\bmod c>\max\{(x+i)\bmod C,(j+y)\bmod C\}$ 的极优数对。显然每次修改影响是 $O(1)$ 的，随便平衡树/权值线段树维护找数对即可。$1\log$。
**42. P6106 [Ynoi2010] Self Adjusting Top Tree**
显然可以差分。一条线段 $((x_1,y_1),(x_2,y_2))$ 对矩形 $(x,y)$ 的贡献是 $\min(\max(0,\min(k_1(x-x_1),k_2(y-y_1)),len)$。
外层的 $\min$ 和次外层的 $\max$ 可以二维数点消掉。内层的取 $\min$ 可以，我草等会半平面加怎么做啊。。
好吧看漏题了，保证任意两条线段没有交点，那么可以枚举 $\min$ 取到了 $x$ 还是 $y$，对线段扫描线（在某一维上的投影点相对位置不变），需要单点修维护区间历史版本和&单点修区间和，可以线段树。
题解里最后一步的做法都好奇怪。是我打开方式不对吗。
**43. P6108 [Ynoi2009] rprsvq**