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 数组的大小与深度有关，所以进行长链剖分即可。
- Title: 2025 年 7 月日祭
- Author: Getaway_Car
- Created at : 2025-07-01 00:00:00
- Updated at : 2026-01-19 20:21:41
- Link: https://getawaycar1024.github.io/article/diary/2025/07/
- License: This work is licensed under CC BY-NC-SA 4.0.