置顶秒删帖。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
者，山间之朝暮也；野芳发而幽香，佳木秀而繁阴，风霜高洁，水落而石出者，山间之四时也。朝而往暮而归，四时之景不同，而乐亦无穷也。
嗯就是看大家都写了做题记录我也不能闲着，所以搞个口胡题记录。
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 ，然后直接查询即可。
对于第二个限制，是一个二维偏序问题，可以将询问离线后扫描线解决。
时间复杂度：O(nlogn)O(n\log n)O(nlogn)，假设 n,m,qn,m,qn,m,q 同阶。
WEEK 7(5.11 / 5.17)
ABC454F（口胡）
Difficulty：4.6 / Medium
Tag：铲雪
显然的，将 AiA_iAi 减去 An−i+1A_{n-i+1}An−i+1 就转化成了一个铲雪问题。
考虑差分法。令 Bi=Ai−Ai−1,B1=A1,Bn+1=−AnB_i=A_i-A_{i-1},B_1=A_1,B_{n+1}=-A_nBi =Ai −Ai−1 ,B1 =A1 ,Bn+1 =−An 。
如果不算对 mmm 取模的话，答案是 ∑∣Bi∣/2\sum |B_i| /2∑∣Bi ∣/2。
现在考虑对 mmm 取模。注意到这个相当于我们可以将若干个 AiA_iAi 预先加上或减去一个 mmm。这个转化成差分数组，就是把若干个 BiB_iBi 加上或减去 mmm，但是加上的个数和减去的个数一定得相同。
所以我们可以把 BBB 排序，然后取前 kkk 个和后 kkk 个进行加 mmm 减 mmm 操作，然后取最小值即可。
O(nlogn)O(n\log n)O(nlogn)。
P16395
Difficulty：4.8 / Easy+
Tag：主席树
这 trick 神了。
我们将集合内的数排名表示出来，会发现，如果一个数出现的数量大于等于 kkk，则其中一个数的排名一定为 kkk 的倍数。
证明：抽屉原理，假设一个数出现的数量大于等于 kkk，设它第一个数的排名对 kkk 取模为 xxx，则它所有排名对 kkk 取模一定包括 [x,x+1,...,x+k−1][x,x+1,...,x+k-1][x,x+1,...,x+k−1] 内每个数对 kkk 取模组成的集合。显然这个里面一定包含 000。
所以，对于这个问题，我们可以通过树上差分，主席树找到排名为 (⌊∣S∣k⌋+1),2(⌊∣S∣k⌋+1),3(⌊∣S∣k⌋+1),...(\lfloor\frac{|S|}{k}\rfloor+1),2(\lfloor\frac{|S|}{k}\rfloor+1),3(\lfloor\frac{|S|}{k}\rfloor+1),...(⌊k∣S∣ ⌋+1),2(⌊k∣S∣ ⌋+1),3(⌊k∣S∣ ⌋+1),... 的数，逐个判断它们出现次数是否大于 ∣S∣k\frac{|S|}{k}k∣S∣ 。
O(nlogn)O(n\log n)O(nlogn)，假设 n,qn,qn,q 同阶。
我去，我写这个常数小到爆了，最大点只跑了 140ms（喜）
ABC458E（口胡）
Difficulty：4.0 / Easy+
Tag：数数
找个时间把式子重新推一下。
首先考虑在 1,21,21,2 序列中插入 333。显然 333 只能插在两个 222 之间。所以我们如果知道了一个序列有多少连续个 222，就能通过隔板法求出有多少种插入 333 的情况了。
直接求总数是困难的，考虑求多少个序列满足 222 的连续段个数为 iii，然后计算。
我们可以分成这四种情况：
* 1,2,1,2,11,2,1,2,11,2,1,2,1，即 222 被 111 包裹。这样有 i+1i+1i+1 个地方要填 111，iii 个地方要填 222，这也是个隔板法，就不算了。
* 1,2,1,21,2,1,21,2,1,2，iii 个地方要填 111，iii 个地方要填 222。
* 2,1,2,12,1,2,12,1,2,1，iii 个地方要填 111，iii 个地方要填 222。
* 2,1,22,1,22,1,2，i−1i-1i−1 个地方要填 111，iii 个地方要填 222。
预处理组合数即可做到 O(n)O(n)O(n)。
ABC458F（口胡）
Difficulty：4.5 / Easy
Tag：AC 自动机上 DP
可惜了哥们只能给你 4.5，要是 AC 自动机一定要 O(n)O(n)O(n) 实现的话就 4.7 了。
考虑给原串建一个 AC 自动机。
为什么一定要 AC 自动机呢？别的不行吗？
因为 AC 自动机有一个神级性质恰好可以解决这个问题：它可以 O(∑∣S∣)O(\sum |S|)O(∑∣S∣) 末尾添加字符，求出当前文本串与所有模式串的匹配状态。
而懂得 AC 自动机的都知道，每个节点都对应着一个状态，总状态数不超过 O(∑∣S∣)O(\sum |S|)O(∑∣S∣)。
那怎么判断是否被包含呢？我们可以对当前的状态一直跳 fail，如果发现某一个地方能匹配了，就说明不行。
所以就可以根据这个建一个图，fi,jf_{i,j}fi,j 表示状态 iii 是否可以到达 jjj。
然后发现就是一次走 nnn 步合法情况。可以 O(poly(∑∣S∣)+(∑∣S∣)3logn)O(\text{poly}(\sum |S|)+(\sum |S|)^3\log n)O(poly(∑∣S∣)+(∑∣S∣)3logn) 解决。
