置顶秒删帖。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
者，山间之朝暮也；野芳发而幽香，佳木秀而繁阴，风霜高洁，水落而石出者，山间之四时也。朝而往暮而归，四时之景不同，而乐亦无穷也。
嗯就是看大家都写了做题记录我也不能闲着，所以搞个口胡题记录。
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) 的，瓶颈在于树状数组，跑得飞快。
record：https://www.luogu.com.cn/record/276503077
Bonus：注意到本题的 mmm 特别小，请尝试以 O(nlogn+mlog2m)O(n\log n+m\log^2 m)O(nlogn+mlog2m) 的时间复杂度解决这个问题，并抢到最优解。
WEEK 6(5.6 / 5.10)
疑似没做题。 如做。
ABC457
Diffiiculty：4.0 / Easy+
1h40min 没调出来一道绿。我真的是人类吗。
注意到区间 [s,t][s,t][s,t] 能被覆盖，当且仅当至少满足以下两个条件之一：
* 存在 i,ji,ji,j 满足 i≠j,s=Li≤Ri≤t,s≤Lj≤Rj=t,Ri+1≥Lji\not=j,s=L_i\le R_i\le t,s\le L_j\le R_j=t,R_i+1\ge L_ji=j,s=Li ≤Ri ≤t,s≤Lj ≤Rj =t,Ri +1≥Lj 。形如下图：
::::info[情况 1]
::::
* 存在 i,ji,ji,j 满足 i≠j,s=Li≤Lj≤Rj≤Ri=ti\not= j,s=L_i\le L_j\le R_j\le R_i=ti=j,s=Li ≤Lj ≤Rj ≤Ri =t。形如下图：
::::info[情况 2]
::::
我们分类讨论两种情况。
情况 1
i≠ji\not= ji=j 有点烦人，考虑去掉这个限制。
我们可以将限制改为 s=Li≤Ri<ts=L_i\le R_i\red{\lt} ts=Li ≤Ri <t，s≤Lj≤Rj=ts\le L_j\le R_j=ts≤Lj ≤Rj =t。这样如果满足限制，那么 Ri<RjR_i\lt R_jRi <Rj ，i,ji,ji,j 一定不相等。
但是这个限制会漏计算 Li=Lj=s,Ri=Rj=tL_i=L_j=s,R_i=R_j=tLi =Lj =s,Ri =Rj =t 的情况。但又注意到满足情况 2，所以不影响。
我们可以开一个数据结构，记录以 iii 为左端点，可能的右端点，与以 iii 为右端点，可能的左端点。显然这个数据结构可以用 2m2m2m 个 set 实现。
查询时，我们只需要找到以 sss 为左端点，右端点 <t\lt t<t 的最大值，以及以 ttt 为右端点，左端点 ≥s\ge s≥s 的最小值，比较这两个的大小即可。
情况 2
i≠ji\not= ji=j 有点烦人，考虑去掉这个限制。
我们可以将这个限制改为两个限制：
* 存在 iii 满足 s=Li,Ri=ts=L_i,R_i=ts=Li ,Ri =t。
* 存在至少 222 个 iii 满足 s≤Li≤Ri≤ts\le L_i\le R_i\le ts≤Li ≤Ri ≤t。
显然和之前的限制等价。
对于第一个限制，我们开个 set 记录 Li,RiL_i,R_iLi ,Ri ，然后直接查询即可。
对于第二个限制，是一个二维偏序问题，可以将询问离线后扫描线解决。
::::success[code]
::::
时间复杂度：O(nlogn)O(n\log n)O(nlogn)，假设 n,m,qn,m,qn,m,q 同阶。
