本文将同步发表于洛谷（暂无法访问）、CSDN 与 Github 个人博客。
2025.1
2025.1.4 新的一年
今日歌曲：New Year’s Day
去年停课的时候是有记日祭的，但是有一些是手写的，一直都还没有整理好。今天看到一个简单的trick，想记下来。于是，就又开始写日祭了。
[洛谷 P2831] [NOIP2016 提高组] 愤怒的小鸟
一道远古状压题了。（一是指题目本身远古，二是指这道题是好久之前就该做的题。）看到第一篇题解的trick，想起去年暑假集训的时候也有这样一个trick，但是忘了是哪道题。这个trick挺简单的，但也挺好用：状压时，如果目标状态是全0或全1，并且转移顺序不影响结果，那么可以直接从最低位的1或0转移，因为最低位最终一定会被转移，而顺序又不影响结果，所以这样做可以优化掉
的复杂度。其他的按正常状压即可。 -
今天学了 SOSDP，挺神奇的一种 DP。这个题算是板子题吧。只用维护子集的最大值与次大值即可。
今天下午给初二机房的办了一场比赛，整体比较顺利。（所以没做什么题。）比赛链接：CWOI ER 1 & NYR。
今天感觉要掉橙了，但是Rated的比赛还要等一周。想着把之前那篇被打回的题解改了交了，但是晚上写给初二机房的的题解了，没空。看明天改吧。
2025.1.10 新的开始
今日歌曲：Castles Crumbling
今天考完期末，回来一看，天塌了，掉橙了。明天打一场比赛。
现在终于确定15班后续的各种事项了。又是一个新的开始。
另外，我就莫名奇妙地进省选了（尽管是体验名额）。还有一个有趣的事实：
我没有提高组一等奖，然而我进了NOIP（体验名额）；我没有NOIP一等奖，但我进了省选（体验名额）。
期待人生中的第一场SCOI（希望不要爆零）。
2025.1.12 言而无信
今日歌曲：Back To December （好吧其实是存货）
我果然是一个言而无信的人。踩一脚前天的日祭，昨天还是没打比赛。
今天%你赛，除了暴力的B和C，其它全挂了分。至于A，调试的时候把模数写掉了。被暴扣70分呜呜呜。
最终荣获
A - 括号序列
题目：给一个由左右括号构成的字符串
，对于每一个位置 ，输出有多少个子串，满足这个子串是一个合法的括号序列，并且 这个位置在子串中。 题解：简单维护前缀与后缀的括号数量即可。（忘写该死的模数暴扣70pts。）
C - 矩阵删除
题目：给一个
的 01 矩阵，我们想在每一行删除一个元素，得到一个 的矩阵。其中删除的元素的位置 ，满足 。请问最后能得到多少种不同的矩阵。两个矩阵如果删除的元素位置不同，但最后得到的结果相同，我们认为是相同的。由于答案很大，输出答案对 取模的值。 题解：比较板的DP，但是赛时思路没那么清晰，也没去推式子。分别维护对于每一个位置的方案数以及与旁边位置重合的方案数，推出式子后发现全都是求和，于是用前缀和维护即可。
2025.1.13 乐极生悲
今日歌曲：Wonderland
今天期末考试考完了，整体还行，语文更是考到了惊人的
下午体育课，刚好初一体锻放歌，放得全是霉霉的歌，我还去点了几首。开心。
然而下课要集合的时候，我小跑了一下，而这下就恰好被足球爆头，眼镜镜架直接断掉，箍牙的铁丝直接断掉，嘴皮直接被铁钉磨得烂掉，鼻子被眼镜压了一个印子，还在流鼻血。
真是乐极生悲。
2025.1.17 傻子游戏
今日歌曲：Foolish One
今天开始上课六天。
昨天听说 jmr 拿了清华一等约。祝贺他。
这周二（1.14）已经回到15班了。
昨天晚上玩梗发癫，还玩了离谱的傻子游戏。达成成就：在5.5h里睡够8h。
上午%你赛，T1忘了判零挂了10pts，T3是之前做过的一道原题，于是赛时死磕，最后没调出来。赛时的思路基本上是对的，但是没想到容斥；又因为我钦定的一个条件有问题，导致正确性略有问题，最后没调出来。
喜提
A - 串
题目：在虱子王国，一句话由
个词组成，其中恰好有 个词是怪的，其它的词都不是怪的。众所周知，负负得正，我们定义一句话的一个区间是怪的，当且仅当其中含有奇数个怪词。请构造一句符合条件的话，使得其中怪的区间数量最多。 题解：发现答案为奇数块乘上偶数块。构造即可。
B - 艺术家
题目：给定一个长度为 n 的颜色序列
。再给出 个区间，第 个区间为 ，保证任何两个区间都是不相交或包含的关系。在接下来的 个单位时间内，第 个时间会给定 ，表示将 变为 。请对于每一个区间求出，最早的其中所有颜色都互不相同的时间。 题解：
保证任何两个区间都是不相交或包含的关系。
所以可以把区间建成一棵树。当一个子区间合法，其父区间才有可能合法。在原数轴上维护
表示 之前第一个颜色与 相同的点，则一个区间内部颜色互不相同等价于 。使用线段树维护。对于 的更新，用 set 维护。即可。（难写死了，还没写完。） C - 黑白树 （[Atcoder ARC108F] Paint Tree）
题解：画一个直径上吊着节点的图，讨论一个节点在什么时候可以带来贡献。容斥计算即可。
晚上打了入门赛，可以加咕值了。
晚自习最后10分钟，记一些话。
我的信竞，在进步么？看起来好像是的。要是拿现在的我和一年前的我对比，那已足以
倍杀。但……补过的题还是不会做，码量大一点的又不愿意写，一到晚自习就写不动了，于是写一会儿又开始划水。我倒有一个优点，就是一般不会去刷水题（除了入门赛）。但是，难一些的题……绿题效率低，蓝题想不全于是又看题解，紫题几乎无法独立完成。 最终做了的题似乎是白做。
……
终究还是人的问题。
2025.1.18 正难则反
今日歌曲：Wildest Dream
这两天换了头像。
今天上午VP CodeForces Round 997 (Div. 2)。
[CodeForces 2056A] Shape Perimeter
计算重叠部分即可。
[CodeForces 2056B] Find the Permutation
我们总是建从小节点到大节点的有向边，对这个DAG进行拓扑排序。因为我们有时并不想让一个小节点往大节点连边，所以用堆维护入度为零的点即可。（可恶，赛时多测不清空卡了我一发。）
[CodeForces 2056C] Palindromic Subsequences
挺玄学的构造题。我们希望大概长这样的结构：
这样构造出的答案有
个，可以通过。稍微分讨一下即可。 赛后看了一下题解，发现自己好唐：
[CodeForces 2056D] Unique Median
又是一道正难则反，计算坏的序列的个数。这道题的trick挺巧妙的，但没接触过，确实想不出来。发现长度为奇数的序列一定不是坏的，所以只考虑偶数长度序列。对于一个序列的中位数
，将序列中 的数化为 ，其它的化为 。若最终区间和为 ，那么这个序列就是坏的。另外要注意去重。维护前缀和即可。 [CodeForces 2056E] Nested Segments
组合数学。这个包含或不交的关系恰好和昨天的B差不多。我们想要尽可能多的节点数量，那么需要构造成二叉树。（这里具体不想证明。）对于某一个节点，设其儿子数量为
，则计算 （卡特兰数）即可。
下午先把E题改了，学习了一下吉司机线段树。这东西挺好理解的，写起来也很爽，但就是又臭又长又难调。
-
这道题本来是第二道模板题的，但因为第一题相当于第二题的子问题，所以直接冲着这道题来了。写板子即可。（啊啊啊终于还是讨厌上吉司机线段树了啊。）
今天整理了一些去年的日祭。还没把手写的整理上去。
2025.1.19 简直糖丸
今日歌曲：All You Have To Do Was Stay
今天上午%你赛，T1爆零了，简直糖丸。一共得了
下午给初二讲题，讲得……简直糖丸。
烦球，今天最后几乎啥都没干。
啊不是为什么T1爆炸啊。
2025.1.20 简直乐丸
今日歌曲：Daylight
昨晚又是在5.5h内睡满8h的一晚。
今天上午VP CodeForces Round 998 (Div. 3)。才做四道，糖丸了。
[CodeForces 2060E] Graph Composition
赛时就很唐。并查集查连通并算连通块即可。
[CodeForces 2060F] Multiplicative Arrays
一道很好的DP+组合数学题。赛时推式子感觉推出来了，结果赛后再一看伪了。很容易发现，
，所以DP计算非 元素的情况，再用组合数学即可。 [CodeForces 2060G] Bugged Sort
这个题就挺有意思的。这篇题解感觉讲得比官方题解还要清晰。可以观察到，当
，我们可以任意（正常）交换两组的位置。因此，我们可以将两组数进行翻转。换而言之，进行翻转的次数必须是偶数次。这里记翻转次数为 。我们把较小的数放在 ，较大的放在 。若按 排序后 有序，那么该组数据有解，当且仅当满足这三个条件之一： ，此时可以选择交换奇数组数翻转以改变 的奇偶性，处于“无敌”状态。 ，此时可以翻转全部以改变 的奇偶性。
否则无解。判断即可。
今天下午看了一个2025年度第一个乐子（原帖，内部帖），简直乐丸。
又一个新梗诞生了：
@chen_zhe 管理制度错了就要改，不能让无辜的人以泪洗面，如果管理制度还是这样的话，洛谷将会越来越腐败！！，我大不了就棕名，我要让洛谷知道瞎诬陷的严重性！
2025.1.21 反则难证
今日歌曲：deja vu
今天上午VP CodeForces Round 999 (Div. 1 + Div. 2)，状态还好。
[CodeForces 2061C] Kevin and Puzzle
有点思维的DP，题目挺好的。
[CodeForces 2061D] Kevin and Numbers
又是一道正难则反。我们很难将
合并，那就把 中不合法的进行拆分。用 map 维护即可。其实这道题也好证 ，只是想凑一个小标题罢了。[CodeForces 2061E] Kevin and And
这题有点……难评。为什么字典树过不了啊……
因为
很小，所以对 进行状压，再将 的变化量压进堆里选最大的 个即可。（好吧其实不是特别理解。）
F 听不懂。
附一张梗图。
（这里声明一下，不是 jmr 讲得不好，而是实在听不懂。）
2025.1.22 比特塞特
今日歌曲：Maroon
年前最后一天了。
上午%你赛
A - bins （[洛谷 P6807] [BalticOI 2010 Day2] Matching Bins）
差分即可。
C - candies（[洛谷 P6808] [BalticOI 2010 Day2] Candies）
题解。
2025.2
2025.2.8 水讨论区
今日歌曲：Bigger Than The Whole Sky
今天洛谷讨论区关闭了。（以后不能水讨论区了。）
这个寒假，什么也没干。一看进度，已经和初二的差不多。但是他们第一遍拉得挺快，估计效果不大。
我如果现在回去，在那边又吃不饱。于是，就只有多肝一肝，把之前的进度补上来。
晚上打ABC392。
[Atcoder ABC392E] Cables and Servers
略考细节的题。先找连通块，之后再找每个连通块中的返祖边（即无用的边），再把连通块连通即可。
（可是这题我赛时AC，后来突然想到一个hack。还没改，烦死了。）
2025.2.9 终于战胜
今日歌曲：Holyground
综合题1。
-
神奇搜索题，暴搜+剪枝+略微组合数学即可。
神奇卡常题目，拼尽全力，2700ms+，终于冲进3s。
-
很普通的一道DP题，可是赛时都在想组合数学。
表示到第 位模 的值为 的数中 的数量， 表示到第 位模 的值为 的数的数量，直接转移即可。 [Gym 102428F] Fabricating Sculptures
神奇DP题。最开始看题解都没看懂，一是自己确实不理解是怎么算的，二是题解写得比较简略，看了好久才看懂。
设
表示从上往下一层层放，当前一共放了 个，最下面一层放了 个的方案数。有方程 （希望没写错）。将这个式子拆开再维护前缀和即可。（开了long long见祖宗。） -
很有趣的一道题。很容易发现，两个相邻字符串长度之差（的绝对值）为
或 。暴搜即可。 赛时的想法是，将原字符串平均分，再给
或 的偏移。可是偏移少了一些，虽然没 TLE 但一直 WA，拼尽全力无法战胜。 赛后再改一改，拼尽全力终于战胜。
今天本来说再补补昨天的 F，改改昨天的 E，结果今天的第三题看半天看不懂，昨天的 E 和 F 都没做。
最终今天做了四道题。
感觉心态有点崩。（尤其是看第三题的时候。）
……
2025.2.10 放弃即可
今日歌曲：Peace
综合题2。
今天还做出了一道题。
[Gym 100861E] Extreme Programming
看了题解真的好简单。首先我们先确定这些问题的顺序。推推式子，排序即可。现在，我们不用考虑顺序，只用直接背包，找出最大的
与最小的 即可。 可是这道题不知道哪里写挂了，WA on test 15。**
放弃即可**。[Gym 100217I] Sharing the Sweets
分拆数板子题。（可是我不会。）写板子即可。
-
这题着实简单。设
表示放了 个括号，当前高度为 ，是否到过最高点（深度为 ）的方案数。直接转移即可。 可是赛时想多了，一直在想组合数学。或许先设方程再推会好一些。
赛时还因为多测不清空挂了四发。
今天还举办了 CWOI ER 2 & 1 > 2 Round，感觉对于他们还是太难了。
（今天字符数破
2025.2.11 放弃即可
今日歌曲：Pink Pony Club
模拟赛
B - 刀言刀语 （[洛谷 P6864] [RC-03] 记忆）
今天给的题解以及同学讲解的都是非矩阵做法，可是听得迷迷糊糊。一下午尝试乱搞做法，结果没搞出来，最后，一道题都没改出来，**
放弃即可**。晚上终于学习了矩阵，基本学懂了，这才发现矩阵有多好用。之后又看了这道题的矩阵+线段树做法，终于基本懂了。将这些数据打包成矩阵：
。对于操作一，等同于 。对于操作二，等同于 。对于操作三，若是恢复某个操作，则与操作一二相同；若是删除某个操作，则将这个操作设为单位矩阵（ ），不会对答案产生影响。用线段树维护每个操作对应的矩阵，区间求和（求积）即可。 这道题记得比较详细，毕竟是第一次接触矩阵。
C - 刀妙构造
题目：给定一个长度为
的排列 ，通过尽可能少的操作，使得 。判断是否有解。若有解，输出具体的操作。操作的定义：选择 满足 ，交换 与 。 题解：原本就满足
的位置将原数组分割成若干个块。对于每个块，若是目标的一种排列则有解。设当前块为 ，则依次把数 移到位置 。要注意的是，在移动的过程中，可能会使得其它的 成立。所以我们将这些即将成立的位置先进行偏移，再将当前的数移到目标位置即可。 扩展：尝试在
的时间复杂度内求出有解的排列个数，对 取模。
这几天强度还是比较高，因为跟进度跟得有点吃力了。今天晚上眼睛疼，难受。
2025.2.12 罚时吃饱
今日歌曲：two years
今天上午VP Codeforces Round 1004 (Div. 2)，下午改Codeforces Round 1004 (Div. 1)。上午C题因为少判了一个条件，罚时吃饱了。
[Codeforces 2066A & 2067D] Object Identification
神奇交互题。观察到一个性质：对象
的答案可能是 ，但对象 的答案不可能是 。 若
不是 的一个排列，一定可以找到一个不在 中的数 ，对其与另一个不同的数询问。若是对象 ，因为 没有向任何点连边，所以答案一定为 。若答案不为 ，则是对象 。 若
是 的一个排列，那么找到满足 的 。询问 与 。若是对象 ，那么两个答案应该是相等的，并且都 （因为 ）。然而如果是对象 ，那么当 ，不可能同时存在一条长度至少为 的 到 的路径与一条长度至少为 的 到 的路径（因为 ）。综上所述，若两个答案相等并且都 ，则是对象 ，否则是对象 。 按照题解模拟即可。[Codeforces 2066B & 2067E] White Magic
这题似乎挺简单的，只是赛时看了一眼但是没多想。
首先可以注意到，没有
的子序列一定是合法的，有两个及以上的 的子序列一定是非法的。所以要么选所有非零元素，要么选所有非零元素与一个 。 若是选一个
，显而易见，选最左侧的 是最优的。于是判断这么选是否合法即可。 [Codeforces 2066C & 2067F] Bitwise Slides
很有意思的 DP 题。
我们根据题意可以得出，对于时刻
，记 ，有 。于是对于某个时刻，有这三种状态： 。设 表示这三种状态的情况数，经过推导（具体过程略），可以得出 。发现可以滚动。由于值域较大，用 map 维护 DP 即可。 [Codeforces 2066D1] Club of Young Aircraft Builders (easy version)
有趣的组合数学题。
因为下面的楼层并不会影响上面的楼层，所以从下往上考虑。对于某一个高度，丢飞机的次数最多为
，假设它实际丢 个，则有 种情况。所以设 表示到了第 层楼，已经丢了 个飞机的情况数。有转移方程 。 答案为
。直接 DP 即可。 扩展：求证答案为
。
今天晚上略水……没做题。但是今天一天综合下来……还将就吧。
2025.2.13 笑点解析
今日歌曲：evermore
今天 jmr 终于回来了。
今天学习了李超线段树。
[洛谷 P4097] 【模板】李超线段树 & [HEOI2013] Segment
刚开始学李超线段树，觉得挺简单的。其实它跟吉司机线段树有点像，只是维护的东西要少一些，并且代码更好写。
对于每个节点，考虑维护在它中点处的最高线段编号，那么用类似于吉司机线段树区间取
：若当前线段完全优于原有线段，那么直接替换；若当前线段完全劣于原有线段，那么直接舍弃；若当前线段与原有线段有交点，那么递归更新当前线段较大的那一段。对于查询，直接把路径上所有的线段取 即可。时间复杂度 -
纯堆码量的题。首先这题一眼树链剖分，一眼李超线段树。这题算是很基础的树剖，只是套的是李超线段树。
于是 LCA + 树剖 + 李超线段树 就算是码量炸弹了。也许树剖都这样，只是我没怎么写过。所以……先把模板题写了再说。
-
第一道真正意义上的树剖。之前倒是写过一个有点树剖思想的贪心（但那个好像是长链剖分）。
一共交了四发，笑点解析：前三发线段树没 pushup。由于当时另外没找到问题，于是我严重怀疑是线段树的问题。然后用那个线段树，写了一个线段树的板子，一测挂了，才发现是没写 pushup，糖丸了。
第一次写树剖，稍微参考了一下题解代码，但整体还是自己在写。树剖其实挺好理解的。
写完模板题，该写这道题了。这道题从下午就开始写，一直调到晚上都没调出来，只有明天再补了。
-
今天
今天晚上
2025.2.14 绝世好题
今日歌曲：Red Wine Supernova
今天%你赛，
B - permutation （[Codeforces 1827B2] [加强版] Range Sorting (Hard Version)）
绝世好题之神秘计数（？）题。
又是一道正难则反。容易发现，答案为：
考虑枚举
满足 ，那么 。显而易见， 是 右侧第一个比它大的数，那么 ，其中 满足 是 左侧第一个比它大的数， 是 右侧第一个比 小的数。维护即可。 这题……题解给的用 set 维护，可惜常数太大，被
卡掉了。他又给了个链表的实现，不想看，于是自己开始研究。 由于要求的值都是最近的最大/最小值，所以考虑使用单调栈维护。
与 都非常好求，可是如何求 是个问题。 当时做这道题的时候自己没想出来，后来看原题题解区才懂。做法是，对于前文所提到的
，维护 个集合 ，满足 。接下来倒序遍历 ，对于每个 ，顺序枚举 ，将单调栈中 的数弹出，栈顶元素即为 。在将每个 操作完后，将 加入单调栈。正确性证明如下（部分摘自原题题解）： 记
表示查询 右侧第一个比 小的数。（ 含义同上。）若这个询问弹出了 ，那么 的答案显然不为 。现在需要证明 的答案不为 。 若
，因为 ，所以 可以作为答案，答案不可能是 。 若
，因为 ，所以答案不可能是 。 若
，那么 ，否则 右侧第一个比它的的数不可能是 ，所以 ，答案不可能是 。
终于证完了。按上述步骤维护即可。
这题本来就有一定的思维难度。如果用单调栈，这道题的思维难度就更高了。如果用有的数据结构（比如 set），倒是好想好写，可是
卡常。
因为今天一下午加晚上一直苦攻 T2，所以昨天的题还没来得及补。
今天写得很晚了，准确来说已经第二天凌晨了。今天就到这里。
2025.2.18 无处不在
今日歌曲：I Forgot You Existed
“我无处不在。”——
今天在改游戏那道题，最终决定重构！
2025.2.20 笑点解析
今日歌曲：The Archer
今天还是在改游戏，最后终于还是改出来了。笑点解析又来了。
在
里计算了 。 在线段树中的编号与实际编号混淆了。 另外还有一些很糖的低级错误，比如右儿子写成
之类的。
2025.2.22 显而易见
今日歌曲：wish you were gay
A - 怎么又是先增后减 （[Atcoder joisc2014_b] [JOI Day2 T2] たのしい家庭菜園）
论赛时代码只与正解相差两行，赛时是有多糖。显而易见，一个数要么放左边，要么放右边。若放左边，则需要交换当前数与左边逆序对的个数，右边同理。显而易见，取较小的一侧的答案。用数据结构维护即可。
2025.2.25 数组开小
今日歌曲：mirrorball
-
神秘又简单的差分约束。显而易见，我们只关注在
到 路径上的点，并且 到路径上每个点的距离都是唯一的。那么有 。差分约束即可。 做的时候由于数组开小了，挂了若干发，也是糖丸了。
-
模板题。
2025.2.27 联合省选
今日歌曲：It’s Nice To Have A Friend
今天写了一点联合省选 2025 游记。
-
模板题。
-
不怎么板但码量极小的题。
我们要求的是满足
的无序二元组 的个数。由于我们并不知道 中的具体数值，只知道部分大小关系，又发现我们可以把上述和式转化为差式，所以维护两个数的差的范围即可。
2025.3
2025.3.1&2 正常说话
这两天参加省选。这里用正常的说话方式补充一些有关考试题目的内容。
-
钦定中位数为
，设可重集中小于 的数的个数为 ，等于的是 ，大于的是 ，那么有 ，所以 。为了让 尽量成为中位数，那么考虑让 尽可能大，即能取 的都取 。同时可以得到 的范围，便可判断。用差分维护即可。 -
先考虑打一个暴力，随后发现是区间覆盖（覆盖成
，其中 是给定值， 是下标。）与区间查询。线段树维护即可。（可是我不会告诉你我写的双 可能要挂分。）
2025.3.4 难度偏高
今日歌曲：The Lucky One
今天补了一下 USACO25JAN，铜组难度感觉偏高啊。
[洛谷 P11667] [USACO25JAN] Astral Superposition B
思维题。先处理
B，这两颗星星一定一颗在当前位置，一颗在左上方对应的位置。接下来处理G，如果当前位置能够由已有的星星移动而来，则忽略；否则当前位置需要一个星星。即可。[洛谷 P11672] [USACO25JAN] Table Recovery S
这题一直没改，今天终于改了。先统计出每个数出现了多少次，仅出现了一次的两个数中的一个便是第一个数。又由于第一个数所在的行/列中的每个数的出现次数是不重复的，于是就可以根据第一个数推出整个表格。比较两个答案中更小的一个输出即可。
2025.3.6 正难则反
今日歌曲：Naked In Manhattan
今天中午 C 老师请吃饭，回来就出省选成绩了。省选总分
今天略水。
[洛谷 P11672] [USACO25JAN] Reachable Pairs G
有趣的正难则反。对于
操作，相当于把当前点换成一个超级原点并不参与计数。所以考虑倒推，先建边（并查集合并）再加贡献。具体地，对于一条边 ，若： ：由于两个点都是超级原点，直接合并 所在的块。 ：当枚举到 时合并 所在的块。 ：当枚举到 时合并 所在的块。
枚举到一个点再加入贡献即可。
2025.3.8 打表可得
今日歌曲：Starlight
A - 114514
题目：定义函数
，其中 是一个长度为 的序列。这个函数的值 满足： 的长度为 。 中的元素互不相同。 。 是满足上述条件的序列中，字典序最小的。
现给定
，求有多少个序列 使得 。 题解：__
打表可得_，每个位置可能的值是独立的，即对于任意一个位置， 的取值集合不会随其他值的改变而改变。设 表示值 是否出现过，那么对于 的取值范围就是 ，其中 满足 且 $vis{l - 1} = 0$。并查集维护即可。 C - 深黯「军团」
题目：给定
与一个长度为 排列 。计算从 开始的接下来 个排列的逆序对个数之和。 题解：神秘数位 DP。这题赛时还是想到了许多，但是考试时误认为
的较高位不会改变，所以挂成 分（数据好水）。 赛时想到了通过求一个排列的逆序对来算排名，也想到了要求的就是排名在一个区间内的排列的逆序对数之和，还**
通过打表**想到了全排列的逆序对个数的 DP，甚至还想到了类似于阶乘进制的东西，可是因为不会康托展开而没写出来。具体地，将
与排列 康托展开。由于康托展开的值的数位之和就是逆序对个数，所以答案为 ，其中 表示 的数位之和。对于重复的部分，直接 DP 即可。
2025.3.11 观察样例
今日歌曲：Getaway Car
要改名了。今天 VP Codeforces Round 1008 (Div. 2)，打得烂的一匹，最开始只做了 A 和 B，不过幸好在 2:28 把 E AC 了，不然今天晚上整个人都不好了。
[CodeForces 2077A & 2078C] Breach of Faith
赛时一直在求
，然后就被卡死了。 事实上，发现
更好求一些。 。显而易见，把最大值作为 即可不重复。排序即可。 [CodeForces 2077B & 2078E] Finding OR Sum
神秘交互题。以下均讨论八位整数。观察样例发现，询问
似乎比较有用，可以直接得到 。再 根据直觉，考虑询问，将得到的答案 再减去 就可以得到 的贡献。为了不让每一位的贡献重叠，我们便想到空一个位置放一个 。这样，我们就可以根据这些数位的贡献来算出这些数位的和（指 对应数位之和）。剩下未知的数位也便可以根据 与已知的数位求出。显而易见，求答案时我们并不在意当前数位具体的值，只在意数位和。所以对于 的每一位只用分讨 或 即可。 这种题确实挺直觉的，个人觉得也比较靠运气。
比如我 C 想了半天就是想不到，这题基本是看一眼就有点想法而且就对了，甚至还是一发入魂。
2025.3.15 嗨克数据
今日歌曲：This Is Why We Can’t Have Nice Things
D - 完美的答卷
题目：给定长度为
的数组 ，设 ，求 。 题解：本题数据过水，以至于赛时对拍拍出了问题但是交到 OJ 上过了。赛时这题也想到了许多，可是逻辑并不清晰，最后还是看了题解并与 dpfs 讨论才想出了以下的解法。
钦定
是一个区间的最大值， 是这个区间的最小值，且 。设 表示 左侧第一个比 大的位置，则 ，且 在 的单调（递增）栈中，单调栈 + 01trie 维护即可。可是，上述两个集合的交集不一定从 开始，所以对于 trie 树中的一个节点 ，维护 表示经过该点的数的下标的最大值，便可以解决。可是删除又成为了一个问题。考虑用 vector 暴力维护每个 的历史值，理论上时间复杂度不变，只是常数巨大。 改完之后，就开始造 hack 数据了。似乎有用但不多。
2025.3.18 极限 AC
今日歌曲：Paper Rings
今天 VP Codeforces Edu Round 176。由于准备 VP 时 CF 还在系统测试，所以并不算严格意义上的 VP。最后一共做了 4 道，而 D 是在 VP 1:54 时才 AC，此前还有 3 发罚时。也是极限 AC。
-
先将
排序。发现对于某一种颜色，能够与其搭配的颜色都是连续的一段。所以前缀和并动态维护能够搭配的区间即可。注意略特判 的情况。 [CodeForces 2075D] Equalization
注意到花费不能重复，所以考虑背包 DP。设
表示将 右移 位、将 右移 位的最小代价，转移十分显然，即可 无脑做。然而由于我赛时太有脑了，非要写 ，最后调了好久才过。 下次再也不长脑子了。
2025.3.20 疑似双休
今日歌曲：I Hate It Here
后天不用上课，这周疑似可以双休了！
今天在补好题推荐。
[CodeForces 2078D] Scammy Game Ad
很符合“时下流行”的题目了。
考虑 DP，设
表示从第 个左/右门开始，到最后一个门的最大倍率。转移也是十分显然的。对于第 对门通过加法新产生的人数 ，将答案加上 即可。注意最初还有 个人。
2025.3.22
并不是双休，在家里 VP 模拟赛。
2025.3.25
打 USACO，菜得银组一道都不会。
2025.3.27
[CodeForces 2077C] Binary Subsequence Value Sum
极其有趣的题目了。
显而易见，
，所以一个字符串的权值 。把 换 ，那么 。继续将这个式子化简即可， 这里不再赘述。[CodeForces 2082B] Floor or Ceil
从二进制角度思考，向上取整等同于先加一再右移一位，向下取整则是直接向右移一位。所以，若一个向上取整操作后还有一个向下取整操作，那么这个向上取整操作相当于是无效的。又有在
次操作之后，最大值最多比最小值大一。所以对于最小值，先向上取整再向下取整即可，最大值反之。 [CodeForces 2081A] Math Division
考虑多操作一次的期望。多操作一次，则代表在第
位上产生了进位，又因为 ，所以前 位产生了进位（第 位是最高位）。设 表示前 位进位的期望，则： 直接 DP 即可。
2025.4
2025.4.1 愚人节
今日歌曲：Forever Winter
我的日祭之前断更了一段时间，今天终于补上了。
今天改不动题，于是在出题。
2025.4.6 水讨论区
今日歌曲：Guilty Pleasure
讨论区居然真的回来了，又可以水讨论区了（。
今天 VP Codeforces Round 1015, Div. 1 + Div. 2，赛后结算时，发现机房网络得了 MVP。详见犇犇。
前四题都是沟槽构造，不再赘述。
[Atcoder ABC400F] Happy Birthday! 3
考虑正难则反。问题转化为：
一个环上有
个物品，颜色分别为 ，每次操作选择两个数 使得 ，对 进行“漂白”，即将颜色都设为 。一次操作的代价为 。求将整个环漂白的最小总代价。 先断环为链。设
表示将 漂白的最小代价，那么显然有 。 设
表示使 能够漂白的最小代价，那么显然有 。当 时，有 。 答案即为
。 [Codeforces 2086E] Zebra-like Numbers
确简单的啊，可是自己就是想不到。
考虑计算一个数的斑马值。贪心地，尽量选大的斑马数减即可。
考虑记搜，设
表示 中斑马值为 的数的个数。那么显然有 ，其中 是不大于 的最大的斑马数。具体地， 表示 中斑马值为 的数的个数， 表示 中斑马值为 的数的个数。
2025.4.8 过水了
今日歌曲：it’s time to go
过水了今天。
2025.4.10 证明略
今日歌曲：The Albatross
[Atcoder ARC196A] Adjacent Delete
唐题啊，可是和我相比还是我更唐。
假设
是偶数。如果我们忽略删除相邻数的条件，即可以任选两个数相减，那么答案应该是前 大的数（记作“较大数”）的和减去前 小的数（记作“较小数”）的和。 容易发现，当我们只能选相邻数相减时，依然可以达到这个答案，因为在任意时刻，总存在至少一对较大数与较小数相邻。
当
是奇数，那么一定有一个元素不被选，且这个元素一定在奇数位，这样才能把数组分成长度为偶数的两段。枚举不被选的位置，用对顶堆维护前后两段的答案即可。 [Atcoder パ研合宿2024 第3日 E] Roller Coaster
人类智慧啊。选高度差最大的边即可。证明略。
[Atcoder パ研合宿2024 第3日 G] Bracket Sequence
极一眼啊，大概十分钟切了吧。跟翻转括号序列的一个区间那题差不多，这题还简单一点。
注意到位置
可由 与跟 位置高度相同的位置转移而来。拿一个桶维护后者即可，遇到右括号时记得清零。
2025.4.12 写了跟写了一样
今日歌曲：august
模拟赛。
A - 倒水
题目：有三个容量分别为
的杯子与一个容量为 的一个桶，每次可以： - 把一个杯子灌满；
- 把一个杯子的水倒出去；
- 把一个杯子的水倒到另一个杯子直到这个杯子空了或另一个杯子满了；
- 把一个杯子的水倒到桶里。
对于
中的每一个 ，求要使桶装满水，最少的操作次数。 题解：
发的题解写了跟写了一样。 容易发现，经过转化，可以得到两种操作：向桶里加
单位水与从桶里舀出 单位水回到对应的杯子（后者是操作一与操作三的结合），每次操作的代价都为二。注意到，对于某一个水杯，若我们用它进行的最后一个操作是操作二，那么代价为一，因为不用把舀出来的水倒出去。设 表示桶里有 单位水的最小代价， 表示三个水杯是否最后用于操作二，那么先正着 DP 一遍，即全部使用操作一，再反着 DP 即可。统计答案时应统计 。 B - 让他们连通 （[Codeforces 1706E] Qpwoeirut and Vertices）
居然能场切
。 要让区间
连通，等价于 ， 与 连通。设 表示 与 连通的时间，则答案为 ，可以用 ST 表维护，常数又小又好写。 对于
，考虑启发式合并。在合并时，枚举较小的集合的元素，并判断它是否与另一个集合中的元素相邻即可。赛时因为没判 被硬控了半个小时。
2025.4.15 不想证明
今日歌曲：cardigan
-
无脑做啊，不想证明。
[Atcoder パ研合宿2024 第3日 H] Big XOR Game
这题评分比括号序列还要低。从高到低讨论，对于每一位，设当前位上是
的数的个数是 ，那么有： 1
2
3
4
5if(((cnt + 1) / 2) & 1 and (cnt / 2) & 1 ^ 1) Alice;
if(((cnt + 1) / 2) & 1 ^ 1 and (cnt / 2) & 1) {
if(n & 1) Bob;
else Alice;
}不想详细说明。
2025.4.19 输入挂了
今日歌曲：Sad Beautiful Tragic
TTPD 一周年了。
今天模拟赛因为输入挂了 暴涨暴跌。
A - 说唱入门教学
题目：给定一首歌的歌词（以拼音形式），每两句话一一匹配，
，求出 押的个数。 题解：题面好唐。先把韵母处理出来，然后 trie 树即可。常数极大。
B - 画画入门教学
构造题，手动推一推小样例即可。
2025.5
2025.5.5 了跟了一样
今日歌曲：Fifteen
又断更了半个月。
前几周学了一下 AC 自动机，但是学了跟学了一样。
前几天终于把那套题出完了，但是出了跟出了一样。
昨天考试，听了评讲，但是改了跟改了一样。
晚上打 ARC，但是打了跟打了一样。
[Atcoder ARC197C] Removal of Multiples
唐题啊，但是赛时一直在想整除分块之类的，结果没想出来。
但是这题也就真纯唐，用线段树维护区间内留下的数的数量即可。需要证个上界。
[Atcoder ARC197D] Ancestor Relation
好题啊好题。记
表示矩阵的第 行的内容（用 bitset 维护）。 考虑什么时候有
。因为与孩子有关系的节点一定与祖先有关系，但与祖先有关系的节点不一定与孩子有关系。所以有 或 ，前者对应 是 的祖先，后者则对应 是 的祖先。容易证明这是一个充要条件，那么若 ，则一定不存在 与 。 接下来考虑一种特殊情况：
，此时 在一条没有任何分岔的一条“链”上，那么这条链上的节点的位置就可以互换。设一组 相同的点的数量为 ，那么这一组点可以带来 的贡献。 此外，
，显然需要有 。那么我们就总结出以下三条条件或贡献： 。 或 ，当且仅当 。（等价于： ，当且仅当 或 。） - 对于极多的
个 相同的数，可以带来 的贡献。
于是按以上三点计算即可。
2025.5.18 宇宙射线
由于宇宙射线的影响，这里遗失了一篇日祭。主播不想补日祭了。
前几天又断更了，应该是在补 CQ CCPC 的题吧。主播不想补日祭了。
（我明明写了的，可不知道这篇日祭怎么就消失了。）
2025.5.22 主播不想补日祭
今日歌曲：High Infidelity
前天又学了一下 exgcd。主播不想补日祭了。
今天考试。
A - 三重移位 （[Atcoder ARC136B] Triple Shift）
略为神秘。观察到，进行一次操作后，逆序对个数的变化量一定是偶数，所以
与 的逆序对个数的差值必须是偶数。另外，当 中存在重复的元素，那么相当于可以造一对逆序对出来，此时一定有解。 B - 最小差分和 （[Atcoder ARC147C] Min Diff Sum）
题解。
更好的做法如下：假设当前
有序，那么可以拆贡献。拆下来是 。于是让 尽量小， 尽量大。将 降序排序，将 升序排序即可。（主播不想写了，看不懂就去看原题题解吧。） C - 前缀与后缀 （[洛谷 P9180] [COCI 2022/2023 #5] Slastičarnica）
[To do]
D - 贪吃蛇 （[洛谷 P7078] [CSP-S2020] 贪吃蛇）
[To do]
2025.5.24 竟然草过去了
今日歌曲：You’re on Your Own, Kid
今天叕考试。
A - 红魔乡 （[TopCoder 15693] Fixed Point Reversals）
显然好做。把翻转区间看成交换元素即可，唯一的限制是当交换的两个元素在
的两侧时，这两个元素需要关于 对称。 B - 妖妖梦 （[洛谷 P4576] [CQOI2013] 棋盘游戏）
当且仅当黑棋和白棋出生在一起时，白棋能赢，否则赢家一定是黑棋。那么黑棋就尽量快速解决战斗，白棋就尽量多拖延，所以白棋转移状态时取最大值，黑棋选择状态时取最小值即可。
C - 永夜抄 （[TopCoder 10945] Rectangular Island）
long double还是太玄学了，竟然草过去了。发现左右移动和上下移动其实是相对独立的，所以单独处理即可。设表示在左右方向上移动了 步，还在格子里的概率， 同理，它们是可以 处理出来的。接下来枚举 表示左右方向上移动的次数，那么此时的贡献应该是 。 显然容易维护，可是发现 这东西容易炸掉，又发现在计算 和 时一共恰好迭代了 次，所以在计算 和 时每迭代一次时乘上 即可。 D - 花映冢
题目：给定一个图，点数和边数都是
级别的，可能有环、自环和重边，求是否存在一条从 出发的路径可以经过所有点至少一次。（可以重复经过边或点）。 题解：显然先把自环和重边判了，接下来 Tarjan 缩点，再拓扑排序即可。
2025.5.26
今天补题。见 5.22 与 5.24。
2025.5.29
今日歌曲：Cruel Summer
今天继续补题。见 5.22。
2025.6
2025.6.2 问我怎么挂的
今天做题。
[洛谷 P2833] 等式 & [SGU 106] The equation
板子题啊，可是改了好久。主要死在向下、向上取整时没用
double（因为有负数）。[SPOJ NWERC11A] Binomial coefficients
这道题自己想到了枚举
，二分 ，也想到了会爆 long long，可是没想到枚举。对于
，进行二分；对于 ，枚举即可。 做的时候因为各种小问题挂了
发。 -
挺简单的呀。问我怎么挂的，其实是把
写成 了。还有另外一些小错。（比如步长写错了，还有负数导致的一些奇怪的问题。） 枚举
与每一对人，解 即可。 -
没想到是打表题。打表发现满足要求的九位数有
个，十位数自然就有 个。（原有基础上在开头加一个数。）十位数以上，每多一位，答案自然就 。九位数以下答案为 。
2025.6.3
-
神秘结论题。设
。模拟一个倒推的过程，容易发现，当且仅当 时有解，其中 是奇数， 是整数。若有解，模拟即可。
2025.6.27
也是莫名其妙断更了一个月。
也是终于把别样的 whk 草过去了。
今天补日祭。
欧拉函数、欧拉定理与线性筛专题
- 欧拉函数
- 欧拉定理
- 满足
的数的个数 满足 的个数 。
利用以上结论即可完成：
[Codeforces 1149D] Abandoning Roads
CF 3000* 远古题，洛谷黑，所以也算是首黑吗。
这题复杂度鬼能想出来。
首先先把重边断掉，这样就会形成若干个连通块。将这些连通块“缩点”之后，用 dij 做新图的最小生成树即可。具体地，设
表示当前在第 个点，已经到达的连通块为 的最短路径。显然每个连通块只会被访问一次，所以复杂度是 的。注意到当一个连通块的大小 时，若先离开这个连通块再回到这个连通块，至少要经过 条重边，而走连通块内部只需要最多 条轻边，所以显然不需要考虑这个连通块，因为跑 dij 的时候显然会选择走连通块内部而不会重复经过。那么连通块数量被优化到了 ，时间复杂度 。
2025.6.30
今日歌曲：Down Bad
昨天终于也是稳 1= 了。
这高中语文老师还是非常正常，但是这高中英语老师是比我还抽象。
今天补题。
[Atcoder ARC180D] Division into 3
很久之前一场模拟赛的题了。
一件显然的事情，就是一个区间的最大值
一定会做出贡献。若 放在第二段，那么当第一段与第三段的长度为 时可以取到最小值，用 ST 表维护即可。若 放在第一段，那么当第二段长度为 可以取到最小值。设 ，那么答案即为 。将询问离线再用单调栈与线段树维护 即可。若 放在第三段，则与放在第一段类似。 -
这道题显然是之前记过的，今天终于补了。
2025.7
2025.7.1 好的标题
为什么你不写标题了呀？——@O_v_O
因为没想到好的标题。——@Getaway_Car
另外，注意到，我一月到六月的日祭数量如下：
| 月份 | 数量 | 有标题数量 |
|---|---|---|
我们的日祭正在蒸蒸日下！
[Codeforces 1610G] AmShZ Wins a Bet
CF 3300* 远古题，洛谷黑，所以也算是第二道黑吗。
赛时想到了每次删除的是一段合法的括号序列，可是竟然连最基本的 DP 都没想到，how sweet！
考虑倒序做，设
表示 的答案，那么它可以由 与 转移而来，其中 是能与 匹配的第一个位置。时间复杂度 。 发现比较字符串还是太慢了，所以考虑使用倍增与哈希实现字符串比较，具体实现类似于树上跳 LCA，一直跳直到
跳到边界或者 ，即可知道两者的大小关系。
2025.7.2
-
我还是太唐了，这样的唐题都不会。
设
表示 的子树中， 目前度为 的最大答案。直接转移即可。 -
对于任意两条相邻的边
与 ，答案不会超过 ，因此可以初步确定答案上界 。另外，看到最小值的最大值，很容易想到二分。二分答案 ，那么有对于任意在同一集合内的 ，满足 。转化一下，即对于任意 满足 ，都有 不在同一集合内。那么我们可以把所有满足 的边 建出来，当且仅当新图是一个二分图， 合法。此时时间复杂度为 。又注意到，对于新图中两个点 ，存在关系 ，由于 是原图中相邻两条边权值和的最小值，而 ，这意味着 一定在原图就已经相连。所以只需要从原图上把满足 的边拿出来建为新图即可。时间复杂度 。
2025.7.3
[Codeforces 407D] Largest Submatrix 3
一道唐题，可是竟然不会。
设
表示下界为 、左界为 、右界为 的最小上界。注意到 ，发现在这基础上，还需要满足 。维护 表示第 列中 最后一次出现的位置即可。注意要特判一下 。 -
第一眼感觉这个题好像来财啊。我们把每次操作剩下的左侧的两张牌叫做手牌。考虑什么时候能够产生贡献。
三张新牌相同。此时手牌状态不变。
有两张新牌相同，且手牌中有一张与它们相同。此时会将手牌中的相同的那张打出，并换来新牌中不同的那张。
两张手牌相同，且新牌中有一张与它们相同。此时会打出两张手牌，并换来新牌中不同的两张牌。
上面三项对应的状态更新如下。（
默认取 ） - 直接全局
。 - （假定
） - （假定
与两张手牌相同）
引入通配符
，表示 。以下是无贡献的状态更新。（ 可相互替换。） 容易发现每一轮一共只有
级别的状态更新，所以我们只需要在当前状态的基础上修改即可。另外注意，以上所有操作都是同时进行，所以需要提前存储操作信息。时间复杂度 。
2025.7.4
-
推式子即可。并不想打公式，
详见原题题解。 [Codeforces 1114F] Please, another Queries on Array?
看题的时候没看到，所以想了一会儿直接去看题解了。 要维护区间乘与区间积的欧拉函数，发现区间积可能很大，不能直接分解质因数。所以考虑维护原数的质因子，发现
的质数个数恰好是 ，可以用 long long维护。而一些数的乘积的质因子状态，即其中每个乘数的质因子状态的或和。区间修改也是类似的道理。
2025.7.6 蒸蒸日上
这已经是七月的第
2025.7.7
今天 VP Codeforces Round 1036, Div. 1 + Div. 2。
[Codeforces 2124E] Make it Zero
沟槽的构造题，并不想记严格的证明。大概就是找到一个位置
满足 ，然后分为 三段，设三段的和分别是 ，我们只需要找到一个 使得 ，接下来可以在两步内解决。再把前两步合并，就变为了第一段清空，第二段减去 ，第三段减去 ，剩下的就是第二步。
2025.7.8
模拟赛挂了
第四题不会，所以也没什么题需要改。
2025.7.9
-
要使这条边端点颜色相同，且删掉这条边后图形成二分图，那么这条边在所有奇环中，且不在任意一个偶环中。
考虑建 DFS 树。对于树边，我们可以通过树上差分维护出当前边属于的奇环与偶环数量。对于非树边，根据奇环数量来讨论：若有且仅有一个奇环，则该非树边合法；若有多个奇环，且存在一对奇环没有交集，那么没有树边合法；若有多个奇环，且这些奇环都相交，那么必定会形成更大的偶环，那么没有树边合法。综上所述，只用讨论合法的树边数量，并特判奇环是否只有恰好一个即可。
2025.7.10
B - 树
题意转化后即动态维护树的直径，具体需要支持向树中加点。
考虑当两棵树合并的时候直径会怎样。容易发现，新树直径的端点一定由原树直径的端点产生，一一判断即可。考虑使用线段树维护区间直径，支持单点修改即可。
2025.7.12
线段树合并要把我的左脑和右脑合一起了。
这篇日祭是线段树合并学习笔记，未来会有补充。
线段树合并顾名思义，就是把两棵线段树的信息按照特定的规则合并起来，一般与动态开点配合使用。
线段树合并常用于优化 DP，尤其是树形 DP（与 DAG 上的 DP），用来优化 DP 转移。（或者是一些需要在树 / DAG 上进行信息转移的东西。）
比如一个树形 DP 的转移方程如下：
$$
dp_{u, i} \mathop{\leftarrow}{v \in son(u)} dp{v, ?}
$$
我们需要将儿子的信息转移到父亲上，而每个节点存储的又是一个数组，常规的做法是一一合并，转移的时间复杂度为
而对于一些转移方程，我们会发现合并信息的操作可以用线段树合并来优化。于是我们就将转移的时间复杂度优化为了
具体的，假设现有
可这时我们会发现，开
于是你就写出了线段树合并。
-
首先可以把区间修改通过差分变成单点修改。
对于
，我们需要维护它每种救济粮的数量与最多的救济粮的种类，显然使用线段树维护。因为我们做了树上差分，所以 DFS 的时候要做一次树上前缀和，即将 和 合并起来。 于是就做完了。时间复杂度
，但常数极大。 另外记一种树链剖分的做法，其实就是离线的树剖。
先正常树剖一下，然后你就会得到
个 dfn 序连续的区间。 由于是离线，所以可以用差分标记这些区间。
所有操作结束后，用权值线段树进行一次前缀和即可。
时间复杂度
，常数极小。 【TBD】
2025.7.13
A - [UVA 12170] Easy Climb & [SPOJ CCROSS] Cross Mountain Climb
赛时基本想到了但是没做出来。显然有
的朴素 DP（单调队列优化）。 可以感知到，
。（我也不知道我赛时是怎么感知到的，总之就是感知到了。） 即，
，那么有效的值的个数就来到了 。（为什么我想到了又没做出来呢？因为我思考的时候把 取到 了，然后就不会了。） 进行一下离散化再 DP 即可。
B - [黑暗爆炸 4160] Exclusive Access 2
赛时写了一个没有正确性的乱搞做法，得了 70 pts。
我们可以把原题转化一下，看成把原图分成若干层（若干部，更严格的说法是用反链覆盖原图，即 dilworth 定理），使得每一层内两个点互不直接相连，求最小层数。发现就是求图的色数。先
预处理一个子集是否有直接相连的元素，再 做 DP 即可。
2025.7.14
-
一个做法是直接取
条鹅卵石路。 可是发现这么做没有正确性。
因为容易发现有一些鹅卵石路是必选的。
那么我们可以先做一次 kruskal，并且先选水泥路，再选鹅卵石路。第一次被选中的鹅卵石路就一定包含了必选的鹅卵石路。
所以接下来只用再做一次 kruskal，先取够
条鹅卵石路，再取水泥路。 [洛谷 P8386] [PA 2021] Od deski do deski
看了题解觉得很简单但是自己就是做不起的 DP。
首先容易发现一个合法的序列一定可以表示为若干个首尾相同的串相连。
换句话说，我们可以在一个合法的序列后面再加上一个首尾相同的串以得到一个新序列。
再换句话说，对于任意一个序列，我们可以通过在末尾增加一个特定的元素，让它与原序列中的某个相同元素匹配成一个区间，以让新序列合法。
考虑 DP，设
表示考虑了 ，当前有 个左端点（新数与它们匹配后能使新序列合法，并且它们被匹配一次后依旧可以被匹配），当前序列是否合法的方案数。那么有四种 DP 转移。 ，新加的元素与左端点匹配，原本合法的序列现在依旧合法。 ，原本合法且有 个左端点，现在增加一个无法匹配的元素使它不合法，但增加了一个左端点。 ，原本的序列不合法，现在增加了一个可以匹配的元素，使新序列合法。 ，原本不合法的序列，现在加一个无法匹配的元素，依旧不合法。
答案是
。注意到 ，所以时间复杂度是 。 HJJOI Day2 A 堆
先转化一下题意，看成先插入元素再删除元素。注意到，如果插入的元素是当前的最大元素，那么直接删除它；在这样的条件下，其它被删除的元素一定是单调不增的。所以只需要一个桶与一个指针维护当前的最大元素即可。
-
题解。
[LOJ 6029] [雅礼集训 2017 Day1] 市场
挺有趣的势能线段树。
看到取模、开根这一类运算容易想到势能线段树，除法也是。但这道题的难点就在于难以看出是哪个数据最终会趋于不变。
动用人类智慧，发现是极差。对于加法操作，并不会改变极差，而除法至少可以让极差减半，即在
次内变为 。 先写一个正常的线段树，然后单独实现除法操作。
注意到，当一个区间的极差为
即所有元素相同时，区间除法相当于区间加法，所以直接做一个区间加标记即可。 另一个可以像上面这样处理的情况是，最初极差为
，操作后极差依然为 ，此时区间除法与区间加法也是等价的。 单独讨论一下上述两种情况并直接返回，其它情况继续递归下去即可。
时间复杂度是
，不会证。 在 sjx 的讲义中，还讨论了最初极差为
，操作后极差为 的情况，此时区间除法等价于区间覆盖，所以似乎还要单独实现区间覆盖，导致代码更屎，所以干脆不讨论这种情况，直接暴力递归即可。（甚至可能会赢过两个 lazy tag 的常数。）
2025.7.15
-
终于也是洛谷首黑了。这题的转化好妙啊。
美丽的定义的转化如下：对于任意一个白点，它的子树中都是白点
对于任意一个黑点，它的父亲一定是黑点 所有的黑点构成一个连通块 黑点个数减去黑边个数等于 。当一棵树是美丽的，因为所有黑点构成一个连通块，所以白色连通块的数量等于黑白边的数量。于是我们就可以用一棵线段树维护每个时刻的黑色连通块数量（即黑点个数减去黑边数量）与白色连通块数量（即黑白边数量）。对于每一条边，容易处理出它在哪个时间段是一条黑边（可以给黑色连通块数量带来 的贡献），在哪个时间段是一条黑白边（可以给白色连通块数量带来 的贡献），当然改边也是容易处理的，实际就是撤销一条边再加一条新边。 这个时候还缺了一步。我们要求的并不是每个时刻的白色连通块数量之和，而是黑色连通块数量为
时的白色连通块数量之和。我们可以通过维护黑色连通块数量的 与当黑色连通块数量取到 时对应时刻的白色连通块数量之和 来解决这个问题。修改白色连通块数量时，我们只需要将 加上 即可。由于在第 个时刻（与第 个时刻）黑色连通块数量一定为 ，所以 一定为 。 -
这不是人类智慧是什么？
先考虑离线下来，记
表示位置 被切割的时间，那么依次处理区间 ，就可以做到实时记录 。对于一个区间，发现它在随机数据下，长度会快速减小，且最多被切割 次，所以可以每次直接找到当前区间内 的最小值，然后从最小值对应位置处切割。但是对于非随机数据，一个区间可能会被切割 次（从左往右切），显然不能沿用上面的做法。区间被切割的次数多的原因是有许多切割的位置都很靠近端点，导致长度减小缓慢。所以我们充分发扬人类智慧，对于一些靠近端点的切割操作，直接更新端点；对于一些处于区间中部的切割操作，再沿用上述做法。 可是“靠近端点”具体又应该是处于区间的什么位置呢（比如前
）？或者说“区间中部”的长度应该取到多少，才能既保证正确性又保证时间复杂度呢？ 若中间块太长，则会导致区间长度减小依然缓慢，而当中间块较短时则可保证区间长度较快减小。所以我们要尽可能最小化中间块长度。若中间块太短，在进行一系列对区间两端的切割操作后，我们并不能保证中间块一定会被保留下来；而当中间块长度大于两侧长度时，在进行一系列对区间两端的切割操作后，我们一定可以保证中间块被保留。综上所述，我们只需要将区间三分即可。
具体实现上，我们需要一棵线段树维护
，它需要支持单点修改、区间查询（查询区间中间段的最小值）、查询给定位置左 / 右侧第一个小于给定值的位置（查询两端的切割情况）。对于第二类查询，需要使用线段树二分。对于区间的迭代，只需要按题解模拟即可，先直接更新左右端点，再进行区间切割。时间复杂度 。 [Codeforces 461B] Appleman and Tree
设
表示考虑到第 个点，当前点是否与黑点在一个连通块的方案数。转移时直接考虑是否删除当前边即可。 -
直接考虑染色对答案的贡献。设
表示考虑到第 个点，以当前点位根的子树中有 个黑点的贡献。做一个树上背包，价值是以儿子为根的子树与其他节点能产生的匹配次数（即经过当前边的次数）乘以当前边的权值。注意转移时要控制好变量的上下界，否则会被卡成 。
2025.7.16
踩一脚 2025.1.17，现在比那时候还是有了一些进步。（现在很难想象之前有段时间天天都只考几十分，接近垫底，但是竟然没觉得什么。）
怎么说呢，教练和家长也都给我聊了好多次了，也是该到努力的时候了。我之前确实学习就没有真正用过全力，所以今天教练说我潜力很足，我也这么认为。只是说面临的困难也挺多的，比如我心理上的一些问题。我无法解决，所以只有尝试不想那些事情，尝试逃避问题。
今天上午考试，一道不会。下午应该是因为天气比较热，所以人有些浮躁，状态不是特别好，效率很低，听课也没怎么听进去，一天只做了一道题，也是成为了 HJJOI 集训期间的前缀最小值。
[Codeforces 1967D] Long Way to be Non-decreasing
就当是学习基环树了。
赛时看出来这题与基环树有关，可是居然没看出来是二分（打脸）。
二分答案
，转化为判定性问题，我们需要对 中每个元素操作最多 次使其单调不降。由于目标是单调不降，所以只需要使用一个变量 表示当前 中的最后一个元素，那么一个新元素就需要在 次操作以内变为一个不小于 的数。将 从小到大枚举，找到最小的 满足这个新元素可以在 次操作以内变为 ，若 则无解，否则有解。 那么现在就转化为了计算一个数在几次操作后能变为另一个数。对于所有
建图，此时会形成一个内向基环树森林，我们只需要计算基环树上两点的距离，就是一个数转化至另一个数的操作次数。 对于基环树的处理，可以使用并查集维护连通性，形成环时忽略当前边，使其形成一棵树。计算两点距离时需要分讨一下两点的位置关系。
2025.7.17
这两天状态不好，所以 7.17 和 7.18 都没做什么题，日祭也是 7.19 才补的。
-
长链剖分的主要用法就是求树上
级祖先和优化 DP。优化 DP 就类似于 dsu on tree，只是一个与树的大小有关，一个与树的深度有关。 求树上
级祖先的方法如下：树剖时对于长度为 的链，需要预处理出链顶的 级祖先与 级儿子（即链中元素）。另外还需要预处理出 级祖先。对于每组询问，先向上跳 ，此时当前点所在长链的长度至少为 。接下来再跳到当前链链顶，再向下或向上把剩下的跳了。
2025.7.18
[P4719] 【模板】动态 DP & [P4751] 【模板】动态 DP（加强版） & [P5024] [NOIP 2018 提高组] 保卫王国
三倍经验是个好东西。
并不想记具体的过程，所以就大概记一下。
对于 P4719，可以先写一个朴素的 DP。对于每一次修改，就需要更新从当前点到根路径上的每个点。因为是路径更改，所有考虑
熟练剖粪树链剖分。尝试把原来的 DP 方程写成一种神秘的矩乘形式，然后对于每一次修改就变成了修改路径上轻边的转移方程（矩阵），答案就是整棵树重链上的矩阵的乘积。对于 P4751，我们只需要使用动态开点线段树，对于每一条重链单独开线段树，这样可以减少线段树的查询次数，可以优化至少
的常数。 对于 P5024，容易注意到最小覆盖集 = 全集 - 最大独立集，那么就可以直接做了。对于修改操作，若要强制选则将权值设为极小值，否则将权值设为极大值。注意算出来的答案是改变权值后的答案，所以输出时还要稍微处理一下。
2025.7.21
[洛谷 P8352] [SDOI/SXOI2022] 小 N 的独立集
DP 套 DP 板子。设
表示考虑到点 ，强制不选的答案为 ，不强制不选的答案为 ，直接转移即可。（其实是我不想写。） [洛谷 P5904] [POI 2014] HOT-Hotels 加强版
长链剖分优化 DP 板子。
对于原题，容易写出一个
的 DP，发现 DP 数组的大小与深度有关，所以进行长链剖分即可。
2025.8
这个月的日祭直接写一起了，基本都在补题。
注意到 7 月份后来状态不好。
-
考虑用一棵普通线段树维护，每个节点维护区间的最大值与区间内好的序列的长度，push up 的时候需要写一个类似于线段树二分的东西，时间复杂度
。 [洛谷 P9824] [ICPC 2020 Shanghai R] Fountains
复杂度好神秘的一道题。
自己写写不清楚，所以干脆看题解吧。[洛谷 P6189] [NOI Online #1 入门组] 跑步
显然可以 oeis。本题就是正整数拆分问题。考虑正整数拆分的做法。一种 DP 是设
表示用了 ，当前和为 的方案数，转移是 。另一种 DP 是设 表示选了 个数，当前和为 的方案数，转移是 。发现第一种 DP 与拆分的数的值域有关，第二种与拆分的数的数量有关。所以考虑根号分治，对于 的数进行第一种 DP，其它的进行第二种 DP。 [CWOI 0819 B组] C - 盲盒流水线
注意到这场因为 B 屎一样的题面搞乱了节奏？（不要给自己找借口了。）不过要是 JDS 不提醒我 A 可能要挂完。
题意是区间背包。因为是区间，容易想到用数据结构维护。注意到背包可以
合并，那么写一个普通线段树的时间复杂度是 ，空间复杂度是 。慢的原因是合并次数太多，所以考虑减少合并次数。发现这个过程是静态的，所以选择猫树。可是发现直接猫树的空间复杂度是 ，所以需要把询问离线下来，每个区间单独处理即可。 P13736 [JOIGST 2025] 日本浮现 / Japan Emerges
气死我了怎么绿题都场切不了。（注意到可能是做提高组模拟赛有点膨胀导致的。）
看到连通立马想到并查集（为啥我没立马想到），看到最小立马想到二分答案转化为判定性问题，判定的时候按题意模拟即可，如果两个块会相连就合并起来。
-
注意到祖先的盛开度一定比孩子大，因为如果交换两个点的盛开度会导致答案不增。所以对于每个点，它的美丽度取的点的位置是固定的，所以可以统计对于每个点，它的盛开度会被作为多少个点的美丽度（记作
）。若我们选择 朵花送出，相当于要选若干个点使得 ，最大化 ，发现 一定是一个包含根的连通块，所以直接树上背包即可。 [CWOI 0822 B组] B - 美丽值
题意略。容易想到拆贡献，考虑
一段会被计算多少次。设 中有 个数 ，剩下的 个数 ，那么 会被计算 次。接下来考虑有多少个序列满足上述条件。首先从 个数中选 个数钦定为 ，那么 个数就可以任意在 中生成，剩下 个数同理。所以总答案是 。 [Atcoder ARC101C] Ribbons on Tree
考虑容斥（？，注意到我不会容斥，是怎么考虑到的），答案为
，其中 表示强制断开的边集为 的方案数。注意到断开若干条边后，形成了若干个独立的连通块，那么每个连通块的方案数就是 （当 是偶数时）。所以直接树上背包即可。 [Atcoder ARC153D] Sum of Sum of Digits
好神秘的 DP。
发现难点主要在于进位。设
表示考虑到第 位，上一位有 个数向这一位进了位，目前答案的最小值（不包含当前这一位）。对于每一位，先对 按当前这一位从大到小排序，那么进位的数字一定是 的一个前缀。接下来就是直接转移，枚举进位个数、 当前这一位的值，然后统计当前数位的和与进位个数，再转移到下一位即可。 [CWOI 0824 B组] A - town
题意是将树分为若干个连通块，要求每个连通块的权值的异或和为
，求方案数。 显然容易想到做树上背包，并且记录当前未闭合连通块的异或和。发现未闭合的连通块的异或和一定是
或 ，所以只用设两个状态。需要特判 （赛时被这个 Corner Case 创飞了。） [CWOI 0824 B组] B - str
很显然的 DP，处理 LCP 即可。但是赛时写的什么 KMP 处理 LCP？什么东西？
[CWOI 0824 B组] C - perm
什么惊人的注意力。
显然与置换环有关。把每个置换环拿出来，设大小为
，那么答案就是 ，其中 表示大小为 的置换环的解数，然后出题人注意到 ，特别地， 。
Codeforces Round 1044 (Div. 2)
D - Chicken Jockey
E - I Yearned For The Mines
发现当树是一条链时是容易的（废话），所以考虑先使用最多
次 类操作把树分为若干条链，再用 次操作检查每一条链。考虑如何在限定次数内将树分为链。我们尝试对树上的点分为以下三类： - 链的端点；
- 链的中间点；
- 执行
类操作的点。
我们可以通过一次 dfs 来确定点的类型。具体地，对于点
： - 若
的儿子中存在一个中间点，或存在至少 个端点，那么 是操作点； - 否则，若
的儿子中恰好存在两个端点（且不存在中间点），那么 是中间点； - 否则，
是端点。
于是我们就找出了需要执行
类操作的点集。 F - Flint and Steel
令
。 容易想到一个朴素 DP：设表示炸死 的苦力怕最少需要引燃多少只苦力怕，有转移 ，时间复杂度 。考虑优化，设 表示炸死 的苦力怕最少需要引燃多少只苦力怕，那么 DP 转移就可以通过线段树来优化，实际复杂度 。
Codeforces Round 1045 (Div. 2)
D - Sliding Tree
在 CF Div. 2 D 放极弱的样例的出题人，愿你们的母亲在天堂相遇。
根据直觉容易想到与直径有关，然后就会自然地想到移动直径上的每一棵子树，然而这样是错误的。正确的做法应该是把直径的一端移到子树上，那么操作次数就应该是
，其中 为直径的长度。至于为什么这样是最优的应该口胡一下可以怔出来，但是不想怔了。 E - Power Boxes
实则并不难，只是赛时死磕 D 去了。赛后自己补出来了，虽然用时有点久。
设从
开始的弹跳次数为 ，那么显然有 ，初始值是 。显然会倒着询问。对于 ，若 ，那么我们询问 即可得到 的值。否则，我们可以直接推出 ，但并不知道 的值。注意到，若 ，因为 ，我们一定可以通过一次询问直接确定 。接下来，我们只需要交换 与 ，原来的第 个盒子现在成为了第 个盒子，又有 ，所以我们可以通过一次询问直接确定 。若 ，交换 与 即可。根据上述过程易证需要 次询问。 F - Permutation Oddness
todo
Codeforces Round 1046 (Div. 1, Div. 2)
B - For the Champion
被随机区分导致掉大分了呜呜呜。
注意到赛时就想到了移到角落，然后就不会了，男蹦。
移到两个角落就可以得到
与 了，然后就做完了。 C - By the Assignment
发现一个图是好的的充要条件是，每个环上所有点的点权都应该相同，这等价于每个边双中的点的点权应该相同。特别地，奇环上所有点的点权都应该是
。所以我们只用找出每个边双联通分量，判断其中已确定点的点权是否全部相同，并且是否存在奇环即可。 D1 & D2 - From the Unknown
注意到我赛时基本会 D1 了，然后饭堂了以为自己是错的？然后开始考虑优化，想到了 D2 正解的
？然后最后 D1 & D2 都没做出来？啊？ 设
。对于 D1，容易想到的是第一次询问 个 ，得到 的大致范围 ，满足 （好像赛时就是 推错了，导致没推出 ？）。接下来要确定 的具体值，于是考虑询问 l 1 l 2 l 3 ... l (r - l)，有。 对于 D2，考虑优化。（以下是赛时想法）发现我们没有把
利用起来。于是考虑利用根号分治与数论分块的思想，第一次询问 个 ，若 则说明 ，否则 。若 ，则考虑询问 个 ，此时每个 都对应一个互不相同的 ；否则，沿用 D1 的思想即可。但是发现这样的询问次数依然可以达到 ……（以下是正解）发现以上有些数值取到 时不一定最优，于是重新设常量 表示：第一次询问 个 ，若 则第二次询问 个 。通过暴力可以求出，当 时询问次数可以控制在 以内。若精细实现，询问次数还可以再少一点。
终于把这几天补了的题的日祭都补了。实则补日祭的时候已经九月了？不管了。
2025.9
鲜花 (2025.9.1)
注意到我停课了。
另外注意到我今天上午做了三道题，下午也许是在尝试改上一场 CF 的 Div. 1 E，顺便学习了一下反射容斥。学了之后发现改不出来，于是放弃了，并开始补日祭。总之就是下午一道题都没做？啊？什么效率？但是我不是挺认真的吗？啊？
反射容斥
todo
MX NOIP 3
A - Novelist
略。
B - Bicycle Tour
根据部分分容易想到从小到大一条条加边，并在形成环时做一个链上的 to min。于是先建出原图的最小生成树，然后树剖即可。
C - 数列色ぬり
题解。
D - DequeQL
改不动。
多校杂题选讲 20250905
A - [NOISG 2025 Prelim] Itinerary
考虑直接把
的路径描到树上，计算每一条边会被经过几次，这一步可以用树上差分解决。接下来，若 是起点，我们只用关注 到 的路径，如果在 的基础上加上这一条路径，每条边的经过次数依然 则合法。实现上，从 开始 dfs，记录 到每个点的路径上的每条边的经过次数的最大值即可。 B - [USACO24DEC] 2D Conveyer Belt S
考虑哪些位置是不合法的，显然是环形传送带及其内部。环形传送带是容易找的，但是内部并不好找。于是正难则反，考虑从边缘开始洪水填充，能走到的位置就是合法的位置，剩下的就是不合法的位置。不过对于每个询问都搜索一遍显然会挂，所以考虑倒着处理询问，每次删掉一个传送带，若当前位置原本不合法但四连通有合法的位置，那么从当前位置再次开始洪水填充即可。
-
首先有结论，若机器人
与机器人 最终停在第 行，那么区间 的机器人一定都可以停在第 行，因为机器人 到第 行的过程中一定会经过第 到第 行， 同理。所以可以停在第 行的机器人一定是连续的一个区间。于是考虑对于每个 ，求出可以到达第 行的机器人的区间，于是问题就转化为了用最少的给定区间覆盖询问区间，这个问题可以用 ST 表实现。具体地，设 表示从 开始，使用 个区间，能达到的最右侧的位置。 D - [NOISG 2023 Finals] Curtains
将询问
转化为，判断是否有 。考虑先离线下来并且按 排序，这样就少了一个限制。考虑使用线段树维护从每个位置 能够完整覆盖到的最右侧的位置 ，那么回答询问就变为了单点查询，增加幕布 是对于 区间修改。具体地，对于所有 的位置 ，执行 。发现这个操作难以实现，但是发现多个这样的操作可以合并（具体过程略），所以使用一棵维护 lz tag 的线段树即可。 E - From the Unknown (Hard Version)
略。
G - [HEOI2013] SAO
好神秘的树形 DP。设
表示考虑到 子树，且 在子树中的拓扑序为 时的方案数。转移时根据 关系分讨，再推推式子就可以得到一个 的 DP，然后发现可以前缀和优化，就变成 的了。 -
todo
MX NOIP 4
todo
多校联考 20250906
todo
关于本文
由 Getaway_Car 撰写, 采用 CC BY-NC 4.0 许可协议.