置顶秒删帖。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
者，山间之朝暮也；野芳发而幽香，佳木秀而繁阴，风霜高洁，水落而石出者，山间之四时也。朝而往暮而归，四时之景不同，而乐亦无穷也。
嗯就是看大家都写了做题记录我也不能闲着，所以搞个口胡题记录。
Week 的划分到周末/节假日结束，嗯对。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
WEEK 1（2026.3.31 - 2026.4.6）
P15654 口胡
link。
ABC452E
Difficulty：4.1 / Easy
题意解析：给定两个长度分别为 n,mn,mn,m 的数组 A,BA,BA,B，求 (∑i=1n∑j=1mAiBj(i mod j)) mod 998244353(\sum_{i=1}^n\sum_{j=1}^m A_iB_j(i\bmod j))\bmod 998244353(∑i=1n ∑j=1m Ai Bj (imodj))mod998244353。
枚举 iii 没啥前途，考虑枚举 jjj。
考虑设置阈值 lll，j≤lj\le lj≤l 直接 O(n)O(n)O(n) 暴力。现在考虑 j>lj\gt lj>l。
注意到第三个乘数一定是 1,2,3,4,...,j−1,0,1,2,3,...1,2,3,4,...,j-1,0,1,2,3,...1,2,3,4,...,j−1,0,1,2,3,... 循环，而且循环次数一定不超过 nj\frac{n}{j}jn 次。所以考虑前缀和处理 ∑Ai\sum A_i∑Ai 与 ∑Ai×i\sum A_i\times i∑Ai ×i，然后减一下就行了。
这样就是 O(nl+∑j=l+1mnj)O(nl+\sum_{j=l+1}^m \frac{n}{j})O(nl+∑j=l+1m jn ) 的，lll 取 000 时有 O(∑j=1mnj)=O(nlogm)O(\sum_{j=1}^m \frac{n}{j})=O(n\log m)O(∑j=1m jn )=O(nlogm)。
record
P6572
Difficulty：4.3 / Template
虚树板子题。
虚树板子题不讲如何建虚树等于废话。
如何建虚树？
首先把关键点按 dfn 排序。然后所有相邻两个的 LCA 一定是这棵虚树的关键点。而且用这些就能描述这一棵虚树了。
::::success[证明]
感性理解不难，说白了懒得证。
那这个和废话没啥区别了（逃
::::
然后再把这些点按 dfn 排序，将每个点与它和上个点的 LCA 相连，就是这一整棵虚树了。
::::info[证明]
上个我都没证，你还想让我证这个？
::::
好了，建完虚树就简单了，套个树上差分板子就行了。
O(nlogn+∑slogs)O(n\log n+\sum s\log s)O(nlogn+∑slogs)。
record
不行，写的题还是太多了，再这么搞下去我这个就是做题记录而不是口胡题记录了。
WEEK 2(4.7 / 4.13上午)
发烧了，写不了题了，那咋办。
没事应该可以加时一天。虽然也写不了什么题就是了。
P16256
场切，爽！
Difficulty: 4.0 / Easy+
考虑每一个 iii 的贡献。注意到这个贡献是独立的，不受前面（除 i−1i-1i−1）贡献情况的影响。因此可以单独计算。
定义 pre(Ai)\text{pre}(A_i)pre(Ai ) 为 maxj=1iAj\max_{j=1}^i A_jmaxj=1i Aj ，显然如果满足 pre(Bi−1)≤pre(Ai−1),pre(Bi)>pre(Ai)\text{pre}(B_{i-1})\le \text{pre}(A_{i-1}),\text{pre}(B_i)\gt \text{pre}(A_i)pre(Bi−1 )≤pre(Ai−1 ),pre(Bi )>pre(Ai ) 或 pre(Bi−1)>pre(Ai−1),pre(Bi)≤pre(Ai)\text{pre}(B_{i-1})\gt
\text{pre}(A_{i-1}),\text{pre}(B_i)\le \text{pre}(A_i)pre(Bi−1 )>pre(Ai−1 ),pre(Bi )≤pre(Ai )，则会产生 111 的贡献。把它们分别计作情况 1，情况 2。
情况 1
显然前 i−1i-1i−1 要在 [1,pre(Ai−1)][1,\text{pre}(A_{i-1})][1,pre(Ai−1 )] 之间选，iii 要在 (pre(Ai),n](\text{pre}(A_i),n](pre(Ai ),n] 之间选，剩下的随便选。总情况数为 (pre(Ai−1)i−1)(i−1)!(n−pre(Ai))(n−i)!{\text{pre}(A_{i-1})\choose i-1}(i-1)!(n-\text{pre}(A_i))(n-i)!(i−1pre(Ai−1 ) )(i−1)!(n−pre(Ai ))(n−i)!。
情况 2
前 i−1i-1i−1 都要在 [1,pre(Ai)][1,\text{pre}(A_i)][1,pre(Ai )] 选，但必须至少有一个要大于 pre(Ai−1)\text{pre}(A_{i-1})pre(Ai−1 )。这太难了。
考虑反向统计，总方案数为 (pre(Ai)i−1)(i−1)!{\text{pre}(A_i)\choose i-1}(i-1)!(i−1pre(Ai ) )(i−1)!，不合法的有 (pre(Ai−1)i−1)(i−1)!{\text{pre}(A_{i-1})\choose i-1}(i-1)!(i−1pre(Ai−1 ) )(i−1)!，所以合法的有 [(pre(Ai)i−1)−(pre(Ai−1)i−1)](i−1)!。
再用方案 1 同种方法考虑后面的，总贡献数为 [(pre(Ai)i−1)−(pre(Ai−1)i−1)](i−1)!(pre(Ai)−i+1)(n−i)!(\text{pre}(A_i)-i+1)(n-i)!(pre(Ai )−i+1)(n−i)!。
时间复杂度：O(n)O(n)O(n)。
record
WEEK 3(4.13下午 / 4.19)
P1084 口胡
恭喜口胡题又添一名大将！
Difficulty：4.7 / Easy
无脑考虑二分答案。
显然跳到儿子节点纯何意味，肯定要一直往根跳。
然后会发现这样还不够，因为可能有一些点可以跨过根去支援其它子树。
所以我们每个子树，如果全移到根已经可以守住就全移到根，否则留一个时间最少的，其它全移到根。
然后到根的所有节点剩余时间和到剩下子树的距离比较，看看能不能匹配。
O(nlognlogV)O(n\log n\log V)O(nlognlogV)，但 0 个人想写。
P4690 口胡
https://www.acgo.cn/discuss/study/79254
WEEK 4(4.20 / 4.26)
在线单点改区间数颜色 口胡
侵删。可能会假。
CF2222F 口胡
Difficulty：4.8 / Easy+
Tag：缺一分治，Kruskal 重构数
MST 好题，潘子涵快补。
考虑枚举 mex\text{mex}mex，求出不包含边权为 iii 的连通情况。
于是考虑缺一分治维护这个。
具体地就是缺的那一个在左半边就把右半边加到集合，否则把左半边加到集合，然后递归，显然每个点最多会被加 ⌈log2n⌉\lceil\log_2 n\rceil⌈log2 n⌉ 次，加上可撤并的一个 log\loglog，复杂度是 O(nlog2n)O(n\log^2 n)O(nlog2n) 的。然后和 Kruskal 重构树一样，合并两个集合的时候加一条为 mex\text{mex}mex 的边上去，最后跑一遍 MST 即可。
WEEK 5(4.27 / 5.5)
CF1381B
Difficulty：4.1 / Easy
Tag：背包 DP
https://www.acgo.cn/discuss/study/80279
P3157
做题用时：1h33min
定义一个下标 iii 的价值为三元组 (ti,i,Ai)(t_i,i,A_i)(ti ,i,Ai )，其中 tit_iti 为时间戳，保证 ti≤nt_i\le nti ≤n 且 tit_iti 各不相同。
对于 k=1,2,...,nk=1,2,...,nk=1,2,...,n，求满足 ti,tj≤k,i<j,Ai>Ajt_i,t_j\le k,i\lt j,A_i\gt A_jti ,tj ≤k,i<j,Ai >Aj 的 (i,j)(i,j)(i,j) 个数。
不像标准的三维偏序问题。那 CDQ 分治到底能不能做呢？
我们尝试求出 ti∈[1,k−1]→tj=kt_i\in[1,k-1]\rarr t_j=kti ∈[1,k−1]→tj =k 的贡献，然后做个前缀和即可。
还能拆，显然可以拆成 (ti∈[1,2x1]→tj=k)+(ti∈[2x1+1,2x1+2x2]→tj=k)+...(t_i\in[1,2^{x_1}]\rarr t_j=k)+(t_i\in[2^{x_1}+1,2^{x_1}+2^{x_2}]\rarr t_j=k)+...(ti ∈[1,2x1 ]→tj =k)+(ti ∈[2x1 +1,2x1 +2x2 ]→tj =k)+... 的形式。注意到这里就可以 CDQ 分治批量求出了。
具体实现方式如下：
给定三个数 l,mid,rl,\text{mid},rl,mid,r，现在的问题是如何快速求出对于每个 k∈[mid+1,r]k\in[\text{mid}+1,r]k∈[mid+1,r] 的 ti∈[l,mid]→tj=kt_i\in[l,\text{mid}]\rarr t_j=kti ∈[l,mid]→tj =k 的贡献。
我们只需要开个数据结构，把 ti∈[l,mid]t_i\in [l,\text{mid}]ti ∈[l,mid] 的信息放进去，然后枚举 ti∈[mid+1,r]t_i\in[\text{mid}+1,r]ti ∈[mid+1,r]，查询满足 j<ij\lt ij<i 且 Aj>AiA_j\gt A_iAj >Ai 或 j>ij\gt ij>i 且 Aj<AiA_j\lt A_iAj <Ai 的 jjj 数量即可。显然这是个二维偏序，扫描线树状数组即可。
这样，每次批量查询是 O((r−l)log(r−l))O((r-l)\log (r-l))O((r−l)log(r−l)) 的，再加上 CDQ 分治，总复杂度是 O(nlog2n)O(n\log^2 n)O(nlog2n) 的，瓶颈在于树状数组，跑得飞快。
换成 veB 疑似可以 O(nlognloglogn)O(n\log n\log\log n)O(nlognloglogn)？
换成压位 Trie 疑似可以 O(nlog2nlogw)O(\frac{n\log^2 n}{\log w})O(logwnlog2n )？
昨天晚上梦到什么写什么的，别看，这俩数据结构只能查最值，不能单点加区间查
record：https://www.luogu.com.cn/record/276503077
