2026.1 做题友基

洛谷P14829 [THUPC 2026 初赛] Asian Soul
2026 过的第一题！！
赛时写了个单根号，没过😅
赛后问了下发现双 \(\log\) 要卡常，不妨去抄个单 \(\log\)（单 \(\log\) 怎么也卡）
对于单次询问，记 \(S=\{a_l,a_{l+1},\dots,a_r\},T=S\cup\{u\}\)，对 \(T\) 内的点建虚树，然后从 \(u\) 开始跳父亲，如果这个点去掉上来的那个儿子的子树后，子树里还有 \(S\) 里的点，那么这个点就有贡献，还要判一下 \(u\) 自己有没有贡献。
有一个很好的想法就是，线段树，先把查询挂到线段树上，然后对线段树的每个点建个虚树统计答案。
注意到建虚树要排序，可以用归并做到单 \(\log\)。
最后把 vector 改成链式前向星就行。
洛谷P6782 [Ynoi2008] rplexq
这种题显然是要根分啊！
\(f(x,l,r)\) 表示 \(x\) 子树中 \([l,r]\) 内的个数，答案是 \(f(x,l,r)\times(f(x,l,r)-1)-\sum\limits_{v\in\text{son}_u}f(v,l,r)\times(f(v,l,r)-1)\) 再除个 \(2\)。
把儿子个数小于等于 \(\sqrt n\) 的点叫做好点，其它的是坏点。
对于 \(x\) 是好点的询问，\(f(v,l,r)\) 相当于是问 \([l,r]\) 中有多少个 \(i\) 满足 \(dfn_v\le dfn_i\le dfr_v\)。
把 \([dfn_v,dfr_v]\) 差分一下，dfs 的时候处理查询，因为儿子的子树不交所以能做到线性空间。
对于 \(x\) 是坏点的询问，有一个暴力做法：对于一个儿子 \(v\)，把 \(v\) 的子树里所有点都标记为 \(v\)，然后跑一遍莫队。
这个肯定是过不了的，有一个很神秘的优化就是：把 \(x\) 的儿子中儿子个数前 \(\sqrt n\) 大的点拉去扫描线，然后把剩下儿子的子树内的点标记一下，离散化跑莫队，可以发现离散化后点数的和是 \(O(n)\) 的，然后就能过了。
洛谷P10081 [GDKOI2024 提高组] 新本格魔法少女 / 洛谷P10148 [Ynoi1999] M47升级型“钢铁阿诺”
用询问表示操作序列里的操作，查询表示查询操作。
把查询离线下来扫描线，扫到 \(r\) 的时候对每个 \(l\) 维护 \(l\sim r\) 的答案。
对序列分块，然后分讨。
修改对散块询问的贡献：维护一下每个块最后被修改的时间和每个位置最后被散块修改的时间，就能得到每个位置最后被修改的时间。显然一个修改会对左端点在它之前的查询做出贡献，用一个 \(O(1)-O(\sqrt n)\) 的分块简单维护这个部分的答案就行。
修改对整块询问的贡献：这个部分有点神秘！
如果上次修改是整块修改，那么可以和上面那个部分拼一起，只用记录一个块上次被修改是不是整块修改就行。
如果不是的话，枚举每个块单独算答案。
可以发现，某个位置上的修改对一个查询的贡献是 \(权值\times(加入到查询的整块询问次数-删除到查询的整块询问次数)\)，发现删除和加入本质上是相同的，只是权值互为相反数，然后询问次数可以差分，记录一下到现在的询问次数就行，可以用两个 \(O(\sqrt n)-O(1)\) 分块维护。
还是扫描线，记录一下每个位置上次被修改的时间 \(t_i\)。当前是散块修改 \([l,r]\)，先记录一下区间内 \(t\) 的种类和出现次数，把它们删了，显然删除次数是线性的，然后把这个修改的贡献加上就行，如果上次是整块修改还得把它的贡献加上！如果是整块修改，只需要删东西就行！注意很多个整块修改放一起的情况。
时间复杂度是单根号，显然能过（？
一些卡常小技巧：删东西的时候，可以用 odt 维护一下颜色段，这样会快点。序列分块块长取 \([2800,3200]\)，询问分块块长取 \(2^{10}\) 然后用位运算优化一下。循环展开。
然后就能过了，因为评测机波动所以要多交几次。