666

愚人节限定互动｜假如报错信息学说人话

愚人节限定：假如报错信息学会说人话 hi，AC狗友们，愚人节要到了，连编译器都在开玩笑！CE、WA、RE……，它们不装了！ 🎯 玩法超简单： 在评论区，给任意一个报错状态“写一句内心独白”，让它变得有梗、有戏、有灵魂。 举个栗子🌰： * CE（编译错误）：“兄弟，你分号呢？我等你等了三千年。” 你可以写： * 报错的“真实OS”（内心戏） * 报错和代码的“对话” * 报错给你发的“微信消息” 🎁 奖励 活动截止，评论区符合参与条件的留言 点赞TOP5每人获得：罐头 × 50 随机抽取5人，每人获得 罐头 × 20 ⏰ 时间 即日起至 2026年4月8日 💚 来吧，让那些折磨过你的报错，今天替你“说话”！ 往期互动

不想毕业

不儿怎么一天没上线还上榜了 不是怎么还榜二了 我不就200个世纪没发帖子吗怎么都没人理我了555 我们班同学莫名其妙的开始疯狂找别人签名，我真是不太理解，才刚开学几周啊各位 不过在这种氛围下我也是被感染了 现在处于一种精神分裂的状态，每天晚上睡觉都会把小学所有事在脑子里过一遍，白天跑到学校去依旧平等的烦所有人，然后在某个随机时间点又突然开始放电影，我真是受不了了。。。 所以我的歌单 《记·念》《明天你好》《去明天》《2019予你成歌》 嗯对你不可以怀疑我的人品也不可以怀疑我的歌品

冷知识，CF也复活了

rt。https://www.acgo.cn/submitRecord/problemset/5236995?userId=1590033&questionType=7

消失的下雨天 我好想再淋一遍

同步在洛谷更新 题目难度应该不会很大 括号内的是 CF 难度，如果不是 CF 的题的话可能会根据体感难度来估算一个 CF 难度（ 2026.03.11 天空仍灿烂 / 它爱着大海（周杰伦 花海） 001. CF1656F PARAMETRIC MST (*2600\RED{2600}2600) 未看题解完成，用时 1hr 29min 18s。 注意到 aiaj+t(ai+aj)=(ai+t)(aj+t)−t2a_ia_j+t(a_i+a_j)=(a_i+t)(a_j+t)-t^2ai aj +t(ai +aj )=(ai +t)(aj +t)−t2（恭喜你你做完了这个题最难的一步）。最后的 t2t^2t2 是容易省去的，于是问题可以转化为： > 对于给定的 ttt 值，你可以构造一棵 nnn 个点的完全图，其中两点 (i,j)(i,j)(i,j) 的边权是 (ai+t)(aj+t)(a_i+t)(a_j+t)(ai +t)(aj +t)，记 f(t)f(t)f(t) 为按照上述步骤构造的图的 MST 边权之和，问 f(t)f(t)f(t) 是否是有上界的。 先考虑对于给定的 ttt 值怎么快速求出构造出完全图的 MST 大小。把所有点的点权 aia_iai 按照从小到大的顺序排序，那么显然此时有 a1+t≤a2+t≤…≤an+ta_1+t\le a_2+t\le\ldots\le a_n+ta1 +t≤a2 +t≤…≤an +t。容易想到记 ppp 是满足 ap+t≥0a_p+t\ge 0ap +t≥0 的 ppp 里最小的值，那么直接贪心的把 ap,ap+1,…,ana_p,a_{p+1},\ldots,a_nap ,ap+1 ,…,an 都和 a1a_1a1 连边，a2,a3,…,ap−1a_2,a_3,\ldots,a_{p-1}a2 ,a3 ,…,ap−1 都和 ana_nan 连边，容易证明该贪心策略一定可以得到最优解。 把这个式子写出来，即： ∑i=pna1ai+t∑i=pn(a1+ai)+∑i=2p−1anai+t∑i=2p−1(an+ai)\sum\limits_{i=p}^na_1a_i+t\sum\limits_{i=p}^n(a_1+a_i)+\sum\limits_{i=2}^{p-1}a_na_i+t\sum\limits_{i=2}^{p-1}(a_n+a_i) i=p∑n a1 ai +ti=p∑n (a1 +ai )+i=2∑p−1 an ai +ti=2∑p−1 (an +ai ) 化简式子： a1∑i=1nai+t(n−p+1)a1+t∑i=pnai+an∑i=2p−1ai+t(p−2)an+t∑i=2p−1aia_1\sum\limits_{i=1}^na_i+t(n-p+1)a_1+t\sum\limits_{i=p}^na_i+a_n\sum\limits_{i=2}^{p-1}a_i+t(p-2)a_n+t\sum\limits_{i=2}^{p-1}a_i a1 i=1∑n ai +t(n−p+1)a1 +ti=p∑n ai +an i=2∑p−1 ai +t(p−2)an +ti=2∑p−1 ai 容易发现这个东西如果对 ttt 已知 ppp 那么可以预处理 aaa 序列前缀和然后做到 O(1)O(1)O(1) 计算答案。 但是问题是 ttt 的取值范围是 t∈Rt\in\mathbb Rt∈R，显然无法枚举所有的实数 ttt 来计算答案。考虑缩小最优解的 ttt 的取值集合。这里注意到对 t∈[ai,ai+1]t\in[a_i,a_{i+1}]t∈[ai ,ai+1 ]，ppp 的取值都不会变化，而显然对同一个 ppp 上面的式子是单峰的答案一定取在两个端点上，因此需要判定的 ttt 的集合只有 −a1,−a2,…,−an-a_1,-a_2,\ldots,-a_n−a1 ,−a2 ,…,−an ，而此时显然 ppp 的值也是十分容易求出的。因此该算法时间复杂度优化到 O(n)O(n)O(n) 可以通过该题。 最后剩下答案为 INF 的情况，直接带入 t=∞t=\infint=∞ 和 t=−∞t=-\infint=−∞ 即可简单判定（只需要看此时 ∞\infin∞ 的项的系数是不是 >0>0>0 的即可）。 该算法对于单组数据时间复杂度为 O(n)O(n)O(n)，可以轻松通过该题。 002. CF521D SHOP (*2800\RED{2800}2800) 未看题解完成，用时 34min 7s。 对一个位置而言赋值操作肯定最多进行一次，因此考虑直接贪心。注意到一定存在一个最优策略满足对每个位置，其执行的操作的顺序都是（赋值）-（加法）-（乘法），括号代表一个操作可有可无。证明可以简单 Exchange-Argument Trick 处理。 考虑先把所有的赋值操作对每个位置只保留赋值最大的操作，然后将其全部转化成加法操作，然后再把加法操作排序之后全部转化成乘法操作。乘法操作直接贪心选最大的 mmm 个数执行操作即可。 总时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn) 可以轻松通过该题。 2026.03.12 一路不断失去 / 一生将不断见证 / 看过再多风景眼眸如初清澄（周深 亲爱的旅人啊） 003. CF852A DIGITS（*2500\COLOR{PINK}{2500}2500） 未看题解完成，用时 26min 18s。 有一个简单的贪心策略是直接把每个位置都拆开得到 ∣s∣|s|∣s∣ 个长度为 111 的数字然后直接加起来，但是这个贪心显然是错的。 考虑直接错上加错，以一定概率把两个长度为 111 的数字合并起来（实测概率取 115\frac1{15}151 可以通过）然后再加起来合并，就可以通过这题。 成功率不太会算，但是这一看就很不能卡 :) 004. 暂时不能公开 2026.03.13 好想再问一遍 / 你会等待还是离开（周杰伦 晴天） 005. P15653 [省选联考 2026] 星图 / STARMAP（*33003{\RED{300}}3300） 直接在原图上维护操作是困难的，套路的考虑在图的反图上执行操作，这样问题转化为要求执行操作使得最终图上边的数量最少。 光轨数量的最大值 为了方便计算，该部分的讨论都将在原图的补图上进行。 考虑从奇偶性的方向入手。注意到若一次恰好可以选择 kkk 个点并对其执行操作，则 k=2k=2k=2 需要单独讨论。当 k>2k>2k>2 时： * k≡0(mod4)k\equiv 0\pmod 4k≡0(mod4)，此时点的度数的奇偶性不会发生变化，但边的数量的奇偶性会发生变化，因此此时最少剩下的边的数量即为 [2∤m][2\nmid m][2∤m]。 * k≡1(mod4)k\equiv 1\pmod 4k≡1(mod4)，此时点的度数的奇偶性会发生变化，且边的数量的奇偶性也会发生变化。此时需要进一步分类讨论： * 若 [2∣m]=[2∣∑i=1n[2∤deg⁡i]2][2\mid m]=[2\mid\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}2][2∣m]=[2∣2i=1∑n [2∤degi ] ]，则此时显然可以在不改变奇偶性的前提下把边数删到答案下界 ∑i=1n[2∤deg⁡i]2\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}22i=1∑n [2∤degi ] 。 * 否则： * 若图上所有点的度数都为偶数，则此时最小可以达到的答案是 333。 * 若图上存在点的度数是奇数，则此时最小可以达到的答案为 ∑i=1n[2∤deg⁡i]2+1\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}2+12i=1∑n [2∤degi ] +1。 * k≡2(mod4)k\equiv 2\pmod 4k≡2(mod4)，此时点的度数的奇偶性不会发生变化，且边的数量的奇偶性也不会发生变化，因此此时最少剩下的边的数量即为 000。 * k≡3(mod4)k\equiv 3\pmod 4k≡3(mod4)，此时点的度数的奇偶性会发生变化，但边的数量的奇偶性不会发生变化。最后剩下的边一定是若干个奇数度数的点两两匹配，答案即为 ∑i=1n[2∤deg⁡i]2\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}22i=1∑n [2∤degi ] 。 而 k=2k=2k=2 显然是简单的，必然可以在补图上删空所有的边。 最后用总数 n(n−1)2\frac{n(n-1)}22n(n−1) 减去上面得到的答案就可以得到最终结果。 构造流程 考虑先从特殊情况入手： 0X01 K=2K=2K=2 显然每次操作一条被连起来的边就可以删除该边。 0X02 K=3K=3K=3 此时操作形如每次反转一个三元环。容易想到先简单消去图上所有的环，得到一个森林。 然后对于森林上每一个非单独结点组成的树结构，均可以通过下面的操作让该树最终剩下恰好一条边： * 选择三个点 u,v,wu,v,wu,v,w 满足当前树上存在一条 u↔v↔wu\leftrightarrow v\leftrightarrow wu↔v↔w 的链。 * 对 u,v,wu,v,wu,v,w 三个点做一次操作，此时 vvv 点脱离树结构成为单独点，u,wu,wu,w 两点之间连了一条边。 容易发现这样恰好可以取到前面分析 k=2k=2k=2 部分的答案下界，因此该构造方案可以证明为最优解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 剩下 k>3k>3k>3 的情况。此时考虑先讨论如何构造出简单结构的操作： 0X11 长度为 444 的环 考虑类比 P9841 的套路，通过调用若干次操作得到一个比较简单的操作形式。 考虑执行下面的 444 次操作： * Step 111：x1,x2,…,xk−2,i,jx_1,x_2,\ldots,x_{k-2},i,jx1 ,x2 ,…,xk−2 ,i,j * Step 222：x1,x2,…,xk−2,j,kx_1,x_2,\ldots,x_{k-2},j,kx1 ,x2 ,…,xk−2 ,j,k * Step 333：x1,x2,…,xk−2,k,px_1,x_2,\ldots,x_{k-2},k,px1 ,x2 ,…,xk−2 ,k,p * Step 444：x1,x2,…,xk−2,p,ix_1,x_2,\ldots,x_{k-2},p,ix1 ,x2 ,…,xk−2 ,p,i 执行上面的 444 次操作后，x1,x2,…,xk−2x_1,x_2,\ldots,x_{k-2}x1 ,x2 ,…,xk−2 每个点都和 xxx 内其余点边的关系发生了 444 次反转（即没有发生变化），和 i,j,k,pi,j,k,pi,j,k,p 四个点的边的关系发生了 222 次反转（即没有发生变化）。而 i↔j,j↔k,k↔p,p↔ii\leftrightarrow j,j\leftrightarrow k,k\leftrightarrow p,p\leftrightarrow ii↔j,j↔k,k↔p,p↔i 四条边则恰好被反转了一次（即发生了变化）。 0X12 长度为 NNN 个点的环（2∣N2\MID N2∣N） 这里为了简化操作，定义一个长度为 nnn 的点的环形如： * 对于任意整数 iii 满足 1≤i<n1\le i<n1≤i<n，i,i+1i,i+1i,i+1 两点之间都有一条边。 * 1,n1,n1,n 两点间有一条边。 考虑分类讨论，考虑下面的策略： * 选择 1,2,3,41,2,3,41,2,3,4 四个点执行 K4K_4K4 的操作，这样 2,32,32,3 两个点可以单独脱离环，然后 1,41,41,4 两个点会多出一条连边，得到形如 1−4−5−6−…−n−11-4-5-6-\ldots-n-11−4−5−6−…−n−1 的环。这个操作可以每次从环上单独分离出两个点。 * 重复执行上述操作直到环上点数量 ≤4\le 4≤4 为止。 此时因为 2∣n2\mid n2∣n 所以最终会获得一个长度为 444 的环，直接执行一次上面给出的操作就可以把所有点全部分离，最终剩余 000 条边。 0X13 U↔V↔WU\LEFTRIGHTARROW V\LEFTRIGHTARROW WU↔V↔W 的链（2∣K2\MID K2∣K） 目标是在图中反转 u↔v,v↔wu\leftrightarrow v,v\leftrightarrow wu↔v,v↔w 两条边。考虑先执行下面的操作： * Step 111：x1,x2,…,xk−2,u,vx_1,x_2,\ldots,x_{k-2},u,vx1 ,x2 ,…,xk−2 ,u,v * Step 222：x1,x2,…,xk−2,v,wx_1,x_2,\ldots,x_{k-2},v,wx1 ,x2 ,…,xk−2 ,v,w 此时 u↔v,v↔wu\leftrightarrow v,v\leftrightarrow wu↔v,v↔w 两条边都被反转了，但是此时还额外反转了 u↔xi,v↔xiu\leftrightarrow x_i,v\leftrightarrow x_iu↔xi ,v↔xi （1≤i≤k−21\le i\le k-21≤i≤k−2）这两类边。问题转为再反转一次 u↔xi,v↔xiu\leftrightarrow x_i,v\leftrightarrow x_iu↔xi ,v↔xi 的边。 此时通过 2∣k2\mid k2∣k 可以推导出 2∣k−22\mid k-22∣k−2。因此考虑把 k−2k-2k−2 个点分成 k2−1\frac k2-12k −1 组，第 iii 组点是 (x2i−1,x2i)(x_{2i-1},x_{2i})(x2i−1 ,x2i )。然后考虑使用一开始的“长度为 444 的环”操作，第 iii 次操作反转 (u,x2i−1,v,x2i)(u,x_{2i}-1,v,x_{2i})(u,x2i −1,v,x2i ) 四个点组成的四元环，这样每条多余的边都恰好被反转了一次。最终被反转的边就是 u↔vu\leftrightarrow vu↔v 和 v↔wv\leftrightarrow wv↔w。 0X14 (U,V),(U,W),(V,W),(I,J),(I,K),(J,K)(U,V),(U,W),(V,W),(I,J),(I,K),(J,K)(U,V),(U,W),(V,W),(I,J),(I,K),(J,K) 六条边（两个 K3K_3K3 ） 考虑执行下面的操作： * Step 111：x1,x2,…,xk−2,u,vx_1,x_2,\ldots,x_{k-2},u,vx1 ,x2 ,…,xk−2 ,u,v * Step 222：x1,x2,…,xk−2,u,wx_1,x_2,\ldots,x_{k-2},u,wx1 ,x2 ,…,xk−2 ,u,w * Step 333：x1,x2,…,xk−2,v,wx_1,x_2,\ldots,x_{k-2},v,wx1 ,x2 ,…,xk−2 ,v,w 此时 u↔v,v↔w,u↔wu\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow wu↔v,v↔w,u↔w 三条边均被反转。但是同时 xi↔xjx_i\leftrightarrow x_jxi ↔xj （1≤i<j≤n1\le i<j\le n1≤i<j≤n）这条边也被反转了。但是注意到现在想要构造的操作其实可以看作是两个 K3K_3K3 拼凑起来，现在 u↔v,v↔w,u↔wu\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow wu↔v,v↔w,u↔w 这三条边已经得到了一个 K3K_3K3 ，而反转具有自反性，因此可以考虑再将上面的操作执行一次得到第二个 K3K_3K3 并消去所有额外的边： * Step 444：x1,x2,…,xk−2,i,jx_1,x_2,\ldots,x_{k-2},i,jx1 ,x2 ,…,xk−2 ,i,j * Step 555：x1,x2,…,xk−2,i,kx_1,x_2,\ldots,x_{k-2},i,kx1 ,x2 ,…,xk−2 ,i,k * Step 666：x1,x2,…,xk−2,j,kx_1,x_2,\ldots,x_{k-2},j,kx1 ,x2 ,…,xk−2 ,j,k 此时所有 xi↔xjx_i\leftrightarrow x_jxi ↔xj （1≤i<j≤n1\le i<j\le n1≤i<j≤n）都又一次被反转了，因此两个反转操作被抵消掉。而此时 i↔j,i↔k,j↔ki\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow ki↔j,i↔k,j↔k 三条边则同样被反转一次。因此最后 u↔v,v↔w,u↔w,i↔j,i↔k,j↔ku\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow w,i\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow ku↔v,v↔w,u↔w,i↔j,i↔k,j↔k 这六条边恰好分别被反转一次，其余边均未被反转，也就是反转了两个 K3K_3K3 形态的子图。 注意到此时有 k−2k-2k−2 个辅助点，加上 666 个需要反转操作的点一共需要使用 k−2+4=k+4k-2+4=k+4k−2+4=k+4 个点，因此只有 k+4≤nk+4\le nk+4≤n 即 k≤n−4k\le n-4k≤n−4 时才可以使用该操作。 0X15 (U,V),(U,W),(V,W),(W,I),(W,J),(I,J)(U,V),(U,W),(V,W),(W,I),(W,J),(I,J)(U,V),(U,W),(V,W),(W,I),(W,J),(I,J) 六条边 和 0x14 部分本质相同，此时只需要 k≤n−3k\le n-3k≤n−3 就可以执行该操作。 其实这个地方是可以和 kkk 的取值无关的！其实利用 0x11 中给出的反转四元环操作就可以生成出该操作： * Step 111：用 0x11 给出的操作反转 u,v,i,ju,v,i,ju,v,i,j 四个点组成的四元环。 * Step 222：用 0x11 给出的操作反转 u,w,v,iu,w,v,iu,w,v,i 四个点组成的四元环。 容易发现此时恰好反转了 u↔v,v↔w,u↔w,w↔i,w↔j,i↔ju\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow w,w\leftrightarrow i,w\leftrightarrow j,i\leftrightarrow ju↔v,v↔w,u↔w,w↔i,w↔j,i↔j 六条边。 该结构的最大优势是处理 2∤k2\nmid k2∤k 的情况。 解决原问题 0X21 把原图化为特殊形态 前面已经特判掉了 k≤3k\le 3k≤3 的情况，因此本部分只需要解决 k>3k>3k>3 即可。 此时考虑先从图中找出三个关键点 i,j,ki,j,ki,j,k，并对图进行一些操作，使得图上所有二元组 (x,y)(x,y)(x,y) 若满足不存在 x↔yx\leftrightarrow yx↔y 的边，则这样的二元组 (x,y)(x,y)(x,y) 必然还满足下面两条之一： * x=i,y=jx=i,y=jx=i,y=j 或 x=j,y=ix=j,y=ix=j,y=i * x=kx=kx=k 或 y=ky=ky=k 下面考虑如何执行操作可以得到这种图。考虑执行下面的操作： * 对于每两个点 x,yx,yx,y 满足 x≠i,x≠j,y≠i,y≠j,x≠yx\neq i,x\neq j,y\neq i,y\neq j,x\neq yx=i,x=j,y=i,y=j,x=y，若图上当前没有连接 x,yx,yx,y 两个点的边，则考虑继续分类讨论（111）： * 若图上存在点 zzz 满足 z≠a,z≠b,z≠x,z≠yz\neq a,z\neq b,z\neq x,z\neq yz=a,z=b,z=x,z=y 且 xxx 和 zzz 之间不存在边相连，则反转 z,x,y,iz,x,y,iz,x,y,i 四个点组成的四元环。 * 否则，若图上存在点 zzz 满足 z≠a,z≠b,z≠x,z≠yz\neq a,z\neq b,z\neq x,z\neq yz=a,z=b,z=x,z=y 且 yyy 和 zzz 不存在边相连，则反转 x,y,z,ix,y,z,ix,y,z,i 四个点组成的四元环。 * 否则，直接反转 x,y,i,jx,y,i,jx,y,i,j 四个点组成的四元环。 * 对于每个点 xxx 满足 x≠i,x≠j,x≠kx\neq i,x\neq j,x\neq kx=i,x=j,x=k，考虑分类讨论 xxx 和 i,ji,ji,j 两点的连边关系（222）： * 若 xxx 和 i,ji,ji,j 两点都连了边，则不进行任何处理。 * 否则，若 xxx 和 i,ji,ji,j 两点都没有连边，则对 i,x,j,ki,x,j,ki,x,j,k 四个点执行一次 0x11 给出的操作即可。 * 否则，若 xxx 和 iii 没有连边，则对 i,x,k,ji,x,k,ji,x,k,j 四个点执行一次 0x11 给出的操作即可。 * 否则（即只有 xxx 和 jjj 没有连边），则对 j,x,k,ij,x,k,ij,x,k,i 四个点执行一次 0x11 给出的操作即可。 现在理性的分析一下上面给出的流程都干了什么事。这里为了方便描述，将上述流程分为 1,21,21,2 两个部分分别处理。 对于流程 111 而言：每一次都把端点不为 x,yx,yx,y 的不存在的边连接，并删除了对应的以 x,yx,yx,y 为端点的边。在该流程结束后对于所有不存在连边的 x,yx,yx,y 都有 i=xi=xi=x 或 i=yi=yi=y 或 j=xj=xj=x 或 j=yj=yj=y。 对于流程 222 而言：对于原来可能存在的不存在的边 (x,i),(x,j)(x,i),(x,j)(x,i),(x,j) 进行一次包含其的四元环操作后，(x,i),(x,j)(x,i),(x,j)(x,i),(x,j) 之间的边会被连上，而被删除的边一定形如 (x,k),(i,j),(i,k),(j,k)(x,k),(i,j),(i,k),(j,k)(x,k),(i,j),(i,k),(j,k) 中的一类。 此时显然可以达成该部分想要达成的目标。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 考虑回到问题的开始。在这片题解的最初通过对 k mod 4k\bmod 4kmod4 的值分类讨论得到了答案的上界，下面考虑继续对 k mod 4k\bmod 4kmod4 的值分类讨论并给出最终的构造方案（顺便也证明可以取到答案上界）。 0X22 K≡2(MOD4)K\EQUIV 2\PMOD 4K≡2(MOD4) 从最简单的情况入手讨论。 此时既没有边数量奇偶性的约束条件，也没有点度数的奇偶性约束条件。 这里先考虑没有被连的边的数量是偶数的情况。 考虑在 0x21 部分中找出三个关键点 i,j,ki,j,ki,j,k 后，先将 i,ji,ji,j 两个点连起来（直接用 0x13 操作反转 i↔j,j↔ki\leftrightarrow j,j\leftrightarrow ki↔j,j↔k 两条边即可）。 此时所有二元组 (x,y)(x,y)(x,y) 满足 x,yx,yx,y 之间没有边相连当且仅当 x=kx=kx=k 或 y=ky=ky=k。因为此时没有连的边的数量是偶数所以直接给所有没有连的边另一端点两两分组匹配然后用 0x13 操作反转两条边即可。 而如果没有被连的边的数量是奇数，则在 0x21 修改图的形态之前，直接随便选 kkk 个点执行一次操作即可（容易发现 0x21 部分不会修改边的数量的奇偶性）。 0X23 K≡0(MOD4)K\EQUIV 0\PMOD 4K≡0(MOD4) 其实和 0x22 没有本质区别？ 把 0x22 里第一步调整没有被连的边的奇偶性那一步删掉，后面的部分完全是一样的。 0X24 K≡3(MOD4)K\EQUIV 3\PMOD 4K≡3(MOD4) 这里先考虑没有被连的边的数量是偶数的情况。 考虑在 0x21 部分中找出三个关键点 i,j,ki,j,ki,j,k 后，先将 i,ji,ji,j 两个点连起来（直接用 0x13 操作反转 i↔j,j↔ki\leftrightarrow j,j\leftrightarrow ki↔j,j↔k 两条边即可）。 此时所有二元组 (x,y)(x,y)(x,y) 满足 x,yx,yx,y 之间没有边相连当且仅当 x=kx=kx=k 或 y=ky=ky=k。因为此时没有连的边的数量是偶数所以直接给所有没有连的边另一端点两两分组匹配然后用 0x13 操作反转两条边即可。 但是此时仍然没有达到答案的下界，需要进一步进行操作： * 若存在四个点 x,y,z,wx,y,z,wx,y,z,w 满足 x↔k,y↔k,z↔k,w↔kx\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow k,w\leftrightarrow kx↔k,y↔k,z↔k,w↔k 四条边都不在图中存在，那么用前面 0x15 的操作反转 k↔x,k↔y,k↔z,k↔w,x↔y,z↔wk\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,k\leftrightarrow w,x\leftrightarrow y,z\leftrightarrow wk↔x,k↔y,k↔z,k↔w,x↔y,z↔w 这六条边。 * 此时，若 x,yx,yx,y 两点还满足 x↔k,y↔kx\leftrightarrow k,y\leftrightarrow kx↔k,y↔k 两条边都不存在，且 i,j,ki,j,ki,j,k 三个点得到的三条边只有不超过一条边存在，那么用前面 0x15 的操作反转 k↔i,k↔j,k↔x,k↔y,i↔j,x↔yk\leftrightarrow i,k\leftrightarrow j,k\leftrightarrow x,k\leftrightarrow y,i\leftrightarrow j,x\leftrightarrow yk↔i,k↔j,k↔x,k↔y,i↔j,x↔y 这六条边即可。 这一步操作可以尽可能的减少图上任意一点 xxx 和选出的关键点 kkk 之间不存在边的 xxx 的数目。但是此时出现了两端点都不是 kkk 的边不存在的情况，因此还需要再打一次补丁。考虑观察此时图的性质，容易发现此时图上边的数量一定为偶数条，且用上述方法两端点都不为 kkk 的不存在的边的数量一定是偶数。因此考虑再执行下面的操作： * 若对于图上的结点 xxx，i↔j,i↔k,j↔k,x↔ki\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,x\leftrightarrow ki↔j,i↔k,j↔k,x↔k 四条边都没有连，那么考虑找出 x,i,j,kx,i,j,kx,i,j,k 之外的任意一点 yyy。 * 此时考虑用操作 0x15 来反转 i↔j,i↔k,j↔k,k↔x,k↔y,x↔yi\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,k\leftrightarrow x,k\leftrightarrow y,x\leftrightarrow yi↔j,i↔k,j↔k,k↔x,k↔y,x↔y 六条边（即补齐 i,j,ki,j,ki,j,k 三角形上的边以及一条 kkk 连向外部的边）。 * 若此时 i↔j,i↔k,j↔k,x↔yi\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,x\leftrightarrow yi↔j,i↔k,j↔k,x↔y 四条边都没有连，则用操作 0x15 来反转 i↔j,i↔k,j↔k,k↔x,k↔y,x↔yi\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,k\leftrightarrow x,k\leftrightarrow y,x\leftrightarrow yi↔j,i↔k,j↔k,k↔x,k↔y,x↔y 六条边（即补齐 i,j,ki,j,ki,j,k 三角形上的边以及一条在 i,j,ki,j,ki,j,k 以外的边）。 * 此时再找出点 www 满足 w≠i,w≠j,w≠k,w≠x,w≠yw\neq i,w\neq j,w\neq k,w\neq x,w\neq yw=i,w=j,w=k,w=x,w=y，则若此时 i↔k,x↔k,y↔k,z↔ki\leftrightarrow k,x\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow ki↔k,x↔k,y↔k,z↔k 四条边都没有连，则用操作 0x15 来反转 i↔k,i↔x,k↔x,k↔y,k↔z,y↔zi\leftrightarrow k,i\leftrightarrow x,k\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,y\leftrightarrow zi↔k,i↔x,k↔x,k↔y,k↔z,y↔z 六条边（即补齐 i,ki,ki,k 两点之间的边以及 kkk 外面挂着的三条缺失的边）。 * 若此时 j↔k,x↔k,y↔k,z↔kj\leftrightarrow k,x\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow kj↔k,x↔k,y↔k,z↔k 四条边都没有连，则用操作 0x15 来反转 j↔k,j↔x,k↔x,k↔y,k↔z,y↔zj\leftrightarrow k,j\leftrightarrow x,k\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,y\leftrightarrow zj↔k,j↔x,k↔x,k↔y,k↔z,y↔z 六条边（即补齐 j,kj,kj,k 两点之间的边以及 kkk 外面挂着的三条缺失的边）。 此时图上只有 i↔ji\leftrightarrow ji↔j 的边，以及 kkk 点连向除了 i,j,ki,j,ki,j,k 以外的若干点 xxx 的边不存在。因此考虑再打第三层补丁： * 如果 i↔j,j↔k,k↔vi\leftrightarrow j,j\leftrightarrow k,k\leftrightarrow vi↔j,j↔k,k↔v 都缺边，那么直接反转 i,j,k,vi,j,k,vi,j,k,v 组成的四元环即可。 * 如果 i↔j,i↔k,k↔vi\leftrightarrow j,i\leftrightarrow k,k\leftrightarrow vi↔j,i↔k,k↔v 都缺边，那么直接反转 j,i,k,vj,i,k,vj,i,k,v 组成的四元环即可。 可以证明此时图的边数一定达到了上界。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 而对于奇数的情况，同样的，考虑在 0x21 部分中找出三个关键点 i,j,ki,j,ki,j,k 后，先将 i,ji,ji,j 两个点连起来（直接用 0x13 操作反转 i↔j,j↔ki\leftrightarrow j,j\leftrightarrow ki↔j,j↔k 两条边即可）。 0X25 K≡1(MOD4)K\EQUIV 1\PMOD 4K≡1(MOD4) 其实和 k≡3(mod4)k\equiv 3\pmod 4k≡3(mod4) 的情况也差不多，同样也是少了一个选前 kkk 个点反转的操作。这里就不展开讨论了。 2026.03.14 你为寻找或是告别耗尽一生 / 也足够让人心动（周深 亲爱的旅人啊） 006. CF1734F ZEROS AND ONES（*2500\COLOR{PINK}{2500}2500） 首先有一个经典结论是 Thue-Morse 序列的第 iii 项的值就是 parity⁡(i)\operatorname{parity}(i)parity(i)。因此题目中给出的询问操作其实就是问 ∑i=0m−1parity⁡(i⊕(i+n))\sum\limits_{i=0}^{m-1}\operatorname{parity}(i\oplus(i+n))i=0∑m−1 parity(i⊕(i+n))。 记 S(m,n)=∑i=0m−1parity(i⊕(i+n))S(m,n)=\sum\limits_{i=0}^{m-1}\text{parity}(i\oplus(i+n))S(m,n)=i=0∑m−1 parity(i⊕(i+n))。考虑到有 parity(2x)=1−parity(2x+1)=parity(x)\text{parity}(2x)=1-\text{parity}(2x+1)=\text{parity}(x)parity(2x)=1−parity(2x+1)=parity(x)。因此考虑按照 n,mn,mn,m 的奇偶性分别讨论计算答案： * 2∣n2\mid n2∣n：记 n=2k,m=2q+rn=2k,m=2q+rn=2k,m=2q+r（r∈{0,1}r\in\lbrace0,1\rbracer∈{0,1}），则有 S(m,2k)=2S(q,k)+rparity(q⊕(q+k))S(m,2k)=2S(q,k)+r\text{parity}(q\oplus(q+k))S(m,2k)=2S(q,k)+rparity(q⊕(q+k))。 * 2∤n2\nmid n2∤n：记 n=2k+1,m=2q+rn=2k+1,m=2q+rn=2k+1,m=2q+r（r∈{0,1}r\in\lbrace 0,1\rbracer∈{0,1}），则有 S(m,2k+1)=2q−S(q,k)−S(q,k+1)+r(1−parity(q⊕(q+k)))S(m,2k+1)=2q-S(q,k)-S(q,k+1)+r(1-\text{parity}(q\oplus(q+k)))S(m,2k+1)=2q−S(q,k)−S(q,k+1)+r(1−parity(q⊕(q+k)))。 边界条件是 S(0,n)=S(m,0)=0S(0,n)=S(m,0)=0S(0,n)=S(m,0)=0，记忆化搜索就可以做到 O(log⁡2n)O(\log^2n)O(log2n) 处理单组数据。 007. CF1626F A RANDOM CODE PROBLEM（*2800\COLOR{RED}{2800}2800） 注意到位置和位置之间是相互独立的，因此考虑对每个位置分别计算其期望值。设 fi,jf_{i,j}fi,j 表示当前处理的数值为 iii，进行了 jjj 次操作的不同方案数。转移形如： * fi,j+1←(n−1)fi,jf_{i,j+1}\leftarrow (n-1)f_{i,j}fi,j+1 ←(n−1)fi,j * fi−i mod (j+1),j+1←fi,jf_{i-i\bmod(j+1),j+1}\leftarrow f_{i,j}fi−imod(j+1),j+1 ←fi,j 直接转移时间复杂度为 O(kV)O(kV)O(kV)，考虑进一步优化。注意到用题目中给出的操作，若对 xxx 进行操作，则 xlcm(1,2,…,k−1)\frac x{\text{lcm}(1,2,\ldots,k-1)}lcm(1,2,…,k−1)x 的值在整个操作过程中一定不会发生变化。因此考虑初始把所有 aia_iai 都对 lcm(1,2,…,k−1)\text{lcm}(1,2,\ldots,k-1)lcm(1,2,…,k−1) 取模，此时值域 VVV 变为 lcm(1,2,…,k−1)\text{lcm}(1,2,\ldots,k-1)lcm(1,2,…,k−1)，O(kV)O(kV)O(kV) 的时间复杂度（简单卡常后）就可以通过该题。 至于这里为什么是 k−1k-1k−1 而不是 kkk，你会发现最后一次操作（即 i=ki=ki=k 时）aaa 数组的变化未被统计到 ans 内，所以不需要考虑。 008. CF1679F FORMALISM FOR FORMALISM（*2600\COLOR{RED}{2600}2600） 题意可以转化为：有多少个数不能通过题目中给出的操作使得自己的值变得比最开始更小。 然后考虑如果前一位填了 xxx，而且前面部分全都是合法的，那么后一位可以填哪些数字。假设这里填写了数字 yyy，则： * 如果 x,yx,yx,y 之间不能互相交换，那么很显然可以填写 yyy。 * 如果 x,yx,yx,y 之间可以互相交换，且 x>yx>yx>y，那么很显然不能填写 yyy。 * 否则考虑交换 x,yx,yx,y 两个位置后，yyy 可能可以和 xxx 之前的数继续发生交换，因此 yyy 能填写当且仅当在 xxx 的位置填写 yyy 合法。 然后就可以 dp 了。设 fi,jf_{i,j}fi,j 表示当前考虑了 iii 集合，上一次可以填写的数的集合是 jjj，有多少个合法的前缀数。转移直接枚举下一个位置填的是什么数字即可。最终时间复杂度为 O(nω2ω)O(n\omega2^\omega)O(nω2ω)，其中 ω=10\omega=10ω=10。 009. CF1623E MIDDLE DUPLICATION（*2500\COLOR{PINK}25002500） 因为字典序比较遵循贪心原则，所以考虑直接按中序遍历来贪心处理，即一个点被复制后优先处理其左子树。 此时容易想到下面的贪心流程： * 对于当前访问到的结点 uuu： * 递归访问其左子树 lul_ulu 。 * 若 lul_ulu 需要被复制，则 uuu 也同样需要被复制。 * 否则，若 uuu 复制后可以让答案更优，则 uuu 同样需要被复制。 * 若 uuu 被复制，则递归访访问其右子树 rur_uru 。 容易证明该算法的正确性。直接模拟上述流程可做到时间复杂度 O(n)O(n)O(n) 解决问题。 2026.03.15 因为我刚好遇见你 / 留下足迹才美丽 / 风吹花落泪如雨 / 因为不想分离 / 因为刚好遇见你 / 留下十年的期许 / 如果再相遇 / 我想我会记得你（李玉刚 刚好遇见你） 010. CF1598F RBS（*2400\COLOR{PINK}{2400}2400） 好困难/ll 套路的把左括号看作是 111，右括号看作是 −1-1−1。则显然 iii 位置的前缀是 RBS 的充要条件是： * 不存在 1≤j≤i1\le j\le i1≤j≤i 满足 jjj 位置的前缀和 <0<0<0。 * iii 位置的前缀和为 000。 考虑直接状压 dp，设 fi,jf_{i,j}fi,j 表示当前处理了 iii 集合内的字符串，当前的前缀最小值是 jjj，最多有多少个 RBS 前缀。转移随便处理点东西就可以做到 O(n2n)O(n2^n)O(n2n) 转移。 011. [AGC050A] ATCODER JUMPER（*2300\COLOR{YELLOW}{2300}2300） 十分 adhoc 的题目。考虑直接让 iii 点连 2i2i2i 和 2i+12i+12i+1（以 nnn 为单位循环标号），此时 iii 点走 101010 条边之后可以走到 [1024i,1024i+1024)[1024i,1024i+1024)[1024i,1024i+1024) 范围内的点，显然覆盖了 1∼n1\sim n1∼n 内的所有点。 直接模拟上述流程可以做到时间复杂度 O(n)O(n)O(n) 处理问题。 012. CF1614D1 DIVAN AND KOSTOMUKSHA (HARD VERSION) / CF1614D2 DIVAN AND KOSTOMUKSHA (HARD VERSION)（*2100\COLOR{ORANGE}{2100}2100 / *2400\COLOR{PINK}{2400}2400） 先考虑 D1 怎么做。容易想到记 bucibuc_ibuci 表示 aaa 序列中有多少个数是 iii 的倍数（可以写一个埃筛 O(nlog⁡n)O(n\log n)O(nlogn) 求出），然后记 fif_ifi 表示当前序列的 gcd⁡\gcdgcd 为 iii，所有前缀的 gcd⁡\gcdgcd 的和最大是多少。看上去没有记录当前选择了多少个数不好处理，但是注意到处理 fif_ifi 的时候把所有 iii 的倍数加到序列里的贡献都是 iii 且不会对序列的 gcd⁡\gcdgcd 产生影响，而再往后加的话序列的 gcd⁡\gcdgcd 值一定会变小，加入 iii 对答案的贡献也同样会减小，因此计算 fif_ifi 的时候一定需要把所有 iii 的倍数全都加入到序列里。 因此可以想到初始条件为 fi=i×bucif_i=i\times buc_ifi =i×buci ，转移方程为 fi←fij+i(buci−bucij)f_i\leftarrow f_{ij}+i(buc_i-buc_{ij})fi ←fij +i(buci −bucij )（buci−bucijbuc_i-buc_{ij}buci −bucij 即为当前为 iii 的倍数且没有被加入到序列中的元素的数量）。转移的时候枚举 iii 的倍数可以做到 O(Vlog⁡V)O(V\log V)O(VlogV)，能够通过 D1。 此时注意到转移时一个决策 i←iji\leftarrow iji←ij 可能成为不可被替代的最优解当且仅当 jjj 是质数，因此考虑先筛出 1∼V1\sim V1∼V 内所有的质数然后转移的时候只转移质数 jjj 的 dp 值。而处理 bucbucbuc 数组时可以套用 Dirichlet 前缀和的技巧做到 O(Vlog⁡log⁡V)O(V\log\log V)O(VloglogV) 计算。因此总时间复杂度为 O(Vlog⁡log⁡V)O(V\log\log V)O(VloglogV)，简单卡常即可通过 D2。 2026.03.16 泛红的双眼 / 对你的爱怎么遮掩 再靠近多些 / 望着你的背影默念 敏感又热烈 / 只想霸占你的世界 我可以付出一切代价 （王澳楠 请和这样的我恋爱吧） 013. CF1582G KUZYA AND HOMEWORK（*2600\COLOR{RED}{2600}2600） 考虑把每个数都分解质因数来统计。枚举右端点 rrr，然后维护一个栈 stkstkstk 表示当前有哪些左端点是合法的，SiS_iSi 表示若只考虑质因数为 iii 的部分有哪些左端点是合法的。则此时若 iii 位置对应的字符是 *，直接把 iii 加入 SjS_jSj 和 stkstkstk 中即可，否则在 SjS_jSj 和 stkstkstk 中把 iii 对应的质因数抵消掉。统计结束后栈 stkstkstk 内的元素数量即为右端点为 rrr 的合法区间数量。 线性筛出 spfi\text{spf}_ispfi 表示 iii 的最小质因数可以做到 O(nlog⁡V)O(n\log V)O(nlogV) 时间复杂度解决问题。 014. P3644 [APIO2015] 巴邻旁之桥（*2400\COLOR{PINK}{2400}2400） 注意到 k∈{1,2}k\in\lbrace 1,2\rbracek∈{1,2}（现在你已经做完了这个题最难的地方），因此猜测是直接分两类讨论。 K=1K=1K=1 可以把问题转化为：找到最小的 xxx 使得 ∑i=1n∣ai−x∣+∑i=1n∣bi−x∣\sum\limits_{i=1}^n|a_i-x|+\sum\limits_{i=1}^n|b_i-x|i=1∑n ∣ai −x∣+i=1∑n ∣bi −x∣ 的值最小。这是经典的贪心模型，直接把 ai,bia_i,b_iai ,bi 合并到一个数组 ccc 中然后升序排序，取 x=cnx=c_nx=cn 即为最优解。证明直接调整法即可。 K=2K=2K=2 类比 k=1k=1k=1 的做法，必然是建两座桥然后左半部分的走坐标的桥，右半部分的走右边的桥，因此容易想到枚举中间的分界点 ppp 然后对两侧分别做 k=1k=1k=1 的处理，可以简单维护有序数组做到 O(n2)O(n^2)O(n2) 求解问题。 考虑优化时间复杂度。考虑记 F(p)F(p)F(p) 为分界点为 ppp 时的答案，但是 F(p)F(p)F(p) 看上去没有单调单峰等性质。一个想法是直接对 F(p)F(p)F(p) 跑模拟退火（我不知道这个能不能过）。注意到其实不需要真的维护两个有序数组，只需要得知两个数组的中位数值即可，因此考虑从左到右扫描所有本质不同的位置 ppp 然后对两个集合做单点插入 / 单点删除操作，并分别维护两个集合的中位数以及 ∑i=1n∣ai−x∣\sum\limits_{i=1}^n|a_i-x|i=1∑n ∣ai −x∣ 的值（已知元素数量和数组中位数值后这个是容易维护的）。用对顶堆来维护即可做到 O(nlog⁡n)O(n\log n)O(nlogn) 通过该题。 015. CF1097G VLADISLAV AND A GREAT LEGEND（*30003\COLOR{RED}{000}3000） f(S)kf(S)^kf(S)k 看上去不太好维护，考虑经典套路斯特林反演： nk=∑i=0kS2(k,i)(ni)i!n^k=\sum\limits_{i=0}^k S_2(k,i)\binom nii! nk=i=0∑k S2 (k,i)(in )i! 于是题目给出的式子可以化为： ∑i=0ki!S2(k,i)∑S⊆{1,2,3,…,n}(f(S)i)\sum\limits_{i=0}^ki!S_2(k,i)\sum\limits_{S\subseteq\lbrace1,2,3,\ldots,n\rbrace}\binom{f(S)}i i=0∑k i!S2 (k,i)S⊆{1,2,3,…,n}∑ (if(S) ) 问题在于对每个 iii 快速计算 ∑S⊆{1,2,3,…,n}(f(S)i)\displaystyle\sum\limits_{S\subseteq\lbrace1,2,3,\ldots,n\rbrace}\binom{f(S)}iS⊆{1,2,3,…,n}∑ (if(S) ) 的值。 考虑这个东西的组合意义，容易发现对每个 iii，其答案可以看作是在 SSS 集合内点组成的虚树的点集上选 iii 条边的方案数。 设 fi,jf_{i,j}fi,j 表示当前处理了 iii 为根的子树内有 jjj 条虚树的边的方案数，转移类似于树上背包合并，时间复杂度为 O(nk)O(nk)O(nk)。统计答案的时候套路的在深度最低的结点上统计即可。实现起来细节比较多。 016. CF1592F2 ALICE AND RECOLORING 2（*2800\COLOR{RED}{2800}2800） 一眼看上去这题十分神秘不可做，因此考虑逐步挖掘其性质。 性质：有用的操作其实只有 1,41,41,4 两种。 证明： 对于 222 操作：则可以先用一次 111 操作操作掉整个左侧，然后再把不包含于她的左上角操作。这样花费的代价为 222，优于 111 次 222 操作的 333 代价。444 操作同理，用 111 操作操作掉整个上侧然后容斥把不包含于她的左上角操作，花费的代价为 222，优于 111 次 333 操作花费的 444 代价。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 然后发现一次操作操作的是一个矩阵，看上去很麻烦，要将其变为对单点做操作。因此考虑对矩阵做二阶差分。这里重定义颜色之间的按位异或： * 相同颜色异或，得到的颜色为 W\texttt{W}W。 * 不同颜色异或，得到的颜色为 B\texttt{B}B。 考虑将其转化为实际的数字意义，即 W\texttt{W}W 代表 000，B\texttt{B}B 代表 111。此时令这个差分的二维数组为 aaa，则考虑一次操作会对新的二维数组 aaa 做怎样的修改。 * 对于一次 111 操作 (x,y)(x,y)(x,y)，则只有 (x,y)(x,y)(x,y) 一个点会取反。 * 对于一次 444 操作 (x,y)(x,y)(x,y)，那么 (x−1,y−1)(x-1,y-1)(x−1,y−1)，(x−1,m)(x-1,m)(x−1,m)，(n,y−1)(n,y-1)(n,y−1)，(n,m)(n,m)(n,m) 四个点都会被取反。 看上去一次 444 操作修改的位置更多，性质或许也会更强一些？于是对其做分析。考虑同时对在同一行上的两个坐标 (x,y1)(x,y_1)(x,y1 ) 和 (x,y2)(x,y_2)(x,y2 ) 做一次 444 操作，则此时 (x,y1),(n,y1),(x,y2),(n,y2)(x,y_1),(n,y_1),(x,y_2),(n,y_2)(x,y1 ),(n,y1 ),(x,y2 ),(n,y2 ) 四个格子被取反了一次，而 (x,m),(n,m)(x,m),(n,m)(x,m),(n,m) 被取反了两次（等于没变）。一共取反了 444 个格子，和做 444 次 111 操作效果等价，花费均为 444。因此其实这种情况可以规避开较为复杂的 444 操作去使用较为简单的 111 操作替代。同一列上的两个坐标 (x1,y)(x_1,y)(x1 ,y) 和 (x2,y)(x_2,y)(x2 ,y) 的情况也同理。换句话说：444 操作操作的任意两个位置横纵坐标必须都不相同。 可以通过类似的手段分析，得到另一个性质更为强大的结论：使用 444 操作对 (x,y)(x,y)(x,y) 做操作比用 111 操作严格好，当且仅当 (x,y),(x,m),(n,y)(x,y),(x,m),(n,y)(x,y),(x,m),(n,y) 三个格子的值都为 111。证明类似于上面一个步骤，如果这三个格子中存在一个格子不为 111 则需要容斥一次翻转操作，即执行两次翻转，花费的代价为 444。而若用 111 操作则只需要不超过 333 的代价就可以达成目标。 分析了这么一大通，那么这个题有应该如何解决呢？考虑到（忘了哪个题）的套路，建一张二分图，把横坐标建在图的左侧，纵坐标建在图的右侧。那么做一次可能合法 444 操作 (x,y)(x,y)(x,y) 就是把左侧点 xxx 向右侧点 yyy 连一条边。用匈牙利算法对该图跑最大匹配，或者建立源汇用 Dinic 算法求解其网络最大流均可。时间复杂度为 O(n3)O(n^3)O(n3) 或 O(n2.5)O(n^{2.5})O(n2.5)（n,mn,mn,m 同阶），而且远远跑不满，所以可以通过。 017. [ARC127E] PRIORITY QUEUE（*2600\COLOR{RED}{2600}2600） 注意到操作的是一个集合，也就是加入元素的顺序不会影响答案。因此直接钦定的加入元素时不会被删除的数和会被删除的树都是从小到大加入的，因此删除操作一定是删除最近一个加入的未被删除的的元素。 因为需要保证每次删除的数都比前面的数要大，而因为前面钦定了删除一个数，这个数必须是上一次操作刚加入的。而又因为两组序列都必须是单调递增的，因此若当前是第 iii 个要被删除的数，前面已经有 jjj 个数一定不会被删除，则第 iii 个被删除的数的值必须严格大于 jjj。 因此考虑 dp。设 fi,jf_{i,j}fi,j 表示第 iii 次删除操作，删除的序列最大值为 jjj，不同集合的数量。则显然有初始条件 f0,0=1f_{0,0}=1f0,0 =1。转移枚举上一个被删除的数 jjj 可以做到 O(n3)O(n^3)O(n3)。注意到限制条件保证了 dp 的合法状态是连续的一段，因此使用前缀和优化可以做到 O(n2)O(n^2)O(n2) 解决问题。 2026.03.17 日记本线条随回忆见笑 / 付出我的一切却装成笑话编造 / 咽下的时光怨当初年少 / 爱没有尾声恨没有前兆 （因你而在的梦 椰蓉面包） 018. CF2204G GRID PATH（*2700\COLOR{RED}{2700}2700） 容易想到设 fk,i,jf_{k,i,j}fk,i,j 表示当前处理了前 kkk 行的染**况，第 kkk 行恰好染色了 [i,j][i,j][i,j] 区间内的所有格子，方案数是多少。然后注意到这个东西的转移可以用矩阵乘法优化，做到 O(m6log⁡n)O(m^6\log n)O(m6logn) 时间复杂度求解。 考虑继续优化。注意到关键性质：对于具有可减性的信息，[l,r][l,r][l,r] 区间的信息可以被表示为 [0,r]+[l,m−1]−[0,m−1][0,r]+[l,m-1]-[0,m-1][0,r]+[l,m−1]−[0,m−1]。此时所有区间都形如 [0,m−1][0,m-1][0,m−1] 整体的前后缀，可以用 2m2m2m 个区间来表示所有区间。转移直接枚举前后缀区间然后再枚举要转移的区间 [l,r][l,r][l,r] 将 [l,r][l,r][l,r] 拆分成三个前后缀区间后分别按系数转移即可，同样可以用矩阵乘法优化。此时算法的时间复杂度被优化到 O(m3log⁡n)O(m^3\log n)O(m3logn)，简单卡常后可以通过该题。 019. CF1622F QUADRATIC SET（*2900\COLOR{RED}{2900}2900） 考虑先随便构造出一个比较大的二次集。 众所周知阶乘可以被拆成若干个数的乘法的形式，因此考虑对每个数拆贡献，得到 ∏i=1ni!=∏i=1nin−i+1\prod\limits_{i=1}^ni!=\prod\limits_{i=1}^ni^{n-i+1}i=1∏n i!=i=1∏n in−i+1。此时考虑对每个 iii 把平方项都拆掉。注意到 nnn 的奇偶性会影响剩下的 iii 的取值，因此考虑对 nnn 的奇偶性分类讨论： 若 2∣n2\mid n2∣n：此时 ∏i=1nin−i+1=2n2n2![∏i=1n2(2i−1)!]2\prod\limits_{i=1}^ni^{n-i+1}=2^{\frac n2}\frac n2![\prod\limits_{i=1}^{\frac n2}(2i-1)!]^2i=1∏n in−i+1=22n 2n ![i=1∏2n (2i−1)!]2。此时若 4∣n4\mid n4∣n 则在集合中删去 n2\frac n22n 元素即可，否则（即 n≡2(mod4)n\equiv 2\pmod 4n≡2(mod4)）则在集合中删去 2,n22,\frac n22,2n 两个元素即可。 2∤n2\nmid n2∤n 时阶乘的前缀积没有这么好的性质，但是注意到此时并不需要要求删除的元素数量尽量少只需要随便找一个比较紧的下界，因此考虑直接把 nnn 从集合中删去，此时转化为 2∣n2\mid n2∣n 的情况。 于是可以得到关键结论：最优的删除策略一定不会删除超过 333 个元素。 因此考虑枚举删除的元素的数量。容易发现删除 0,10,10,1 个元素是容易判断的，因此此时只需要处理删除两个元素是否可行。 注意到平方这个操作看上去十分像异或，即两个质因数可以相互抵消。因此容易想到经典 trick XOR Hash，给每个质因子赋一个权值，然后预处理出 hih_ihi 表示 iii 的所有质因子的权值的 XOR 值。此时一个集合 SSS 是合法的当且仅当 ⨁i∈Sh(i)=0\bigoplus\limits_{i\in S}h(i)=0i∈S⨁ h(i)=0，因此直接把所有的 h(i)h(i)h(i) 扔到 map 里然后随便维护就可以 O(nlog⁡n)O(n\log n)O(nlogn) 判断是否存在合法解。 020. CF1620F BIPARTITE ARRAY（*2800\COLOR{RED}{2800}2800） 注意到若存在三元组 (i,j,k)(i,j,k)(i,j,k) 满足 i<j<ki<j<ki<j<k 且 ai>aj>aka_i>a_j>a_kai >aj >ak ，则此时 i,j,ki,j,ki,j,k 三个点在无向图上构成一个三元环，此时无向图一定不是二分图。若不存在任何一组这样的 (i,j,k)(i,j,k)(i,j,k) 则此时图上不存在环，一定是二分图。 因此数组 aaa 是二分的 的充要条件 即为序列的最长下降子序列长度不超过 222。此时直接 dp 可以做到 O(n3)O(n^3)O(n3) 时间复杂度解决问题。 考虑使用 Dilworth 定理，若一个序列的最长下降子序列长度为 ddd，则其最少可以被划分为 ddd 个不下降子序列（若数组元素互不相同则可以被划分为 ddd 个上升子序列）。因此序列的最长下降子序列长度不超过 222 一条件可以被转化为 aaa 可以被划分为两个上升子序列。 此时可以设 fk,i,j,0/1,0/1f_{k,i,j,0/1,0/1}fk,i,j,0/1,0/1 表示当前处理了前 kkk 个元素，其中第一个上升子序列最后一个元素位置是 iii，第二个上升子序列最后一个元素位置是 jjj，aia_iai 没有取反 / 取反，aja_jaj 没有取反 / 取反是否存在这样的序列。看上去时间复杂度仍然为 O(n3)O(n^3)O(n3)。此时考虑用染色的 trick，有 max⁡(i,j)=k\max(i,j)=kmax(i,j)=k，因此此时只处理 i,ji,ji,j 两个维度可以做到 O(n2)O(n^2)O(n2)。然后套路的判定性问题把一维信息压到答案里变成最优化问题可以做到 O(n)O(n)O(n) 解决。 2026.03.18 我吹过你吹过的晚风 那我们算不算 相拥 可如梦初醒般的两手空空 心也空 我吹过你吹过的晚风 是否看过同样 风景 像扰乱时差留在错位时空 终是空 是空 （艾辰 错位时空） 021. CF1613F TREE COLORING（*2600\COLOR{RED}{2600}2600） 考虑直接容斥计算。记有至少 iii 个点不满足条件的答案为 fif_ifi ，则容斥可得最后的答案即为 ∑i=0n(−1)ifi\sum\limits_{i=0}^n(-1)^if_ii=0∑n (−1)ifi 。而因为点和点的权值互不相同，因此一个点最多只有一个儿子可以不合法。此时套路的把每个点写成一个多项式的形式那么就可以得到 fi=[xi](∣soni∣x+1)(n−i)!f_i=[x^i](|\text{son}_i|x+1)(n-i)!fi =[xi](∣soni ∣x+1)(n−i)!（可以看作是，先钦定 iii 个点一定不合法，剩下的 n−in-in−i 个点的值随便填），分治 NTT 把多项式乘起来即可做到 O(nlog⁡2n)O(n\log^2n)O(nlog2n) 求解答案。 022. CF1612G MAX SUM ARRAY（*2500\COLOR{PINK}{2500}2500） 容易发现原式的值即为：∑i=1m∑j=1ci(2j−ci−1)xi,j\sum\limits_{i=1}^m\sum\limits_{j=1}^{c_i}(2j-c_i-1)x_{i,j}i=1∑m j=1∑ci (2j−ci −1)xi,j ，其中 xi,jx_{i,j}xi,j 表示值为 iii 的第 jjj 个数的位置，要求所有 xi,jx_{i,j}xi,j 恰好不重不漏的取完 1∼∑i=1mci1\sim\sum\limits_{i=1}^mc_i1∼i=1∑m ci 内的所有整数。此时容易想到直接贪心，把所有位置按照对应的系数 2j−ci−12j-c_i-12j−ci −1 从大到小排序然后依次对应从大到小 ∑i=1mci∼1\sum\limits_{i=1}^mc_i\sim 1i=1∑m ci ∼1 内的所有数，容易证明这个贪心策略最优。 第二问也是容易的，发现为了保证上式的值最大，肯定不会交换两个系数不同的数的 xi,jx_{i,j}xi,j 的值，因此直接求出每个数都出现了几次然后把出现次数的阶乘乘起来即可。 但是直接模拟上述流程时间复杂度为 O(∑ci)O(\sum c_i)O(∑ci )（排序可以写桶排优化到 O(n+V)O(n+V)O(n+V)），无法通过。注意到值域很小，所以直接差分加前缀和求出每个系数的出现次数，然后在值域上双指针扫描即可将时间复杂度优化到 O(n)O(n)O(n)。 2026.03.19 夏天的风我永远记得 清清楚楚地说你爱我 我看见你酷酷的笑容 也有腼腆的时候 夏天的风正暖暖吹过 穿过头发穿过耳朵 你和我的夏天风轻轻说着 （温岚 夏天的风） 023. CF1379E INVERSE GENEALOGY（*2800\COLOR{RED}{2800}2800） 容易发现 nnn 为偶数的时候一定无解。而 nnn 为奇数时，特判 n=1n=1n=1，最多可以构造 n−32\frac{n-3}22n−3 个不平衡点，构造方案就直接构造一条链然后给每个点再插一个儿子得到一个毛毛虫树即可。即：i,i+1i,i+1i,i+1 点的子女结点为 i−2i-2i−2 结点。 因此考虑在 kkk 取在上界以内的时候先构造一个 2k+32k+32k+3 个点有 kkk 个不平衡点的树，然后把最底下的一个有 333 个结点的子树扩建成一个完全二叉树。此时最多会新增一个不平衡点。这个时候把编号为 1,31,31,3 两个点的部分扔掉（此时减少了一个不平衡点）然后把这两个点放在一个不会改变不平衡点数量的地方即可。 corner case 是 n=9,k=2n=9,k=2n=9,k=2。此时不存在合法解，k<2k<2k<2 的特殊情况需要单独处理。 024. CF1830D MEX TREE（*2800\COLOR{RED}{2800}2800） 因为 010101 序列的 mex\text{mex}mex 值只有 0,1,20,1,20,1,2 三种不同取值，所以考虑然后 dp：设 fi,j,0/1f_{i,j,0/1}fi,j,0/1 表示当前处理了 iii 点为根的子树内的信息，iii 所对应的同色连通块的大小为 jjj，iii 点写的数字是 0/10/10/1，答案最少减少了多少。那么显然有下面的转移： * fu,i,0←min⁡(fv,j,1+fu,i,0,fv,i−j,0+fu,j,0+ij−i2)f_{u,i,0}\leftarrow \min(f_{v,j,1}+f_{u,i,0},f_{v,i-j,0}+f_{u,j,0}+ij-i^2)fu,i,0 ←min(fv,j,1 +fu,i,0 ,fv,i−j,0 +fu,j,0 +ij−i2) * fu,i,1←min⁡(fv,j,0+fu,i,1,fv,i−j,1+fu,j,1+2(ij−i2))f_{u,i,1}\leftarrow \min(f_{v,j,0}+f_{u,i,1},f_{v,i-j,1}+f_{u,j,1}+2(ij-i^2))fu,i,1 ←min(fv,j,0 +fu,i,1 ,fv,i−j,1 +fu,j,1 +2(ij−i2)) 直接转移看上去时间复杂度为 O(n3)O(n^3)O(n3)，但可以考虑这样的一个策略：直接对树做黑白染色，容易证明该贪心策略答案减少的数量即为 n+∑i=1n[coli=1]≤2nn+\sum\limits_{i=1}^n[col_i=1]\le 2nn+i=1∑n [coli =1]≤2n 也就是 O(n)O(n)O(n) 级别的，而 dp 转移过程中枚举的同色连通块大小 jjj 对答案的减小是 O(j2)O(j^2)O(j2) 级别的，因此枚举的连通块大小只需要到 O(n)O(\sqrt n)O(n ) 级别即可。 剩下部分的转移其实可以看作是一个树上背包的形式，枚举连通块大小只枚举到子树大小即可保证时间复杂度为 O(nn)O(n\sqrt n)O(nn )，可以通过该题。 2026.03.20 如果在噩梦中睁眼 直面着残忍的世界 风拨动了谁的心弦 留恋却来不及告别 如果结局仅剩惨烈 无惧在逆风中破茧 就算那羽翼被撕裂 重回到十九层深渊 （张韶涵 破茧） 025. CF1545C AQUAMOON AND PERMUTATIONS（*2800\COLOR{RED}{2800}2800） 很神秘的题，首先可以证明必然存在合法解。考虑到若某一列上一个数字只出现了一次，那么为了保证最后得到的矩阵是一个拉丁方，这个位置对应的一行排列必须被选择。此时其余和当前被选中排列有至少一位相同的排列都必须被删除。 因为前 nnn 行的矩阵恰好构成了一个拉丁方，因此通过上面的方式删除一个位置必然一次至少删除两行的排列。此时每一列上的数字都至少出现了两次，根据鸽巢原理可知每一列的数字都必须恰好出现两次才能满足条件。此时对于剩下的排列（只保留未删除的数字），不论是你选出来的矩阵还是剩下未被选的矩阵都是一个拉丁方。 此时考虑套路的对关系建图，考虑对每一列上出现的两个相同值的行编号连双向边，可以证明得到的图一定是二分图。因为一条边连接的两行不能同时被选择，因此对二分图的每个连通块，选择行的方案数都是 222。因此设二分图有 kkk 个连通块，答案即为 2k2^k2k。 直接按照上述过程模拟时间复杂度为 O(n3)O(n^3)O(n3)，感觉应该可以用 ds 优化到 O(n2log⁡n)O(n^2\log n)O(n2logn) 但是没啥必要（ 注意到本题只需要计数二分图内连通块的数量即可求出答案，因此实际写的时候可以不显式建出二分图，直接每次删掉一个排列然后再删掉所有和当前排列有关联的排列即可。 026. CF1404D GAME OF PAIRS（*2800\COLOR{RED}{2800}2800） 考虑先写个暴力 dfs 程序打表，可以发现下面的关键结论： * 若 nnn 是偶数，则先手必胜。 * 若 nnn 是奇数，则后手必胜。 下面考虑证明结论： 2∣N2\MID N2∣N 打表可以发现先手把 i,i+ni,i+ni,i+n 两个元素分为一组，此时后手无论在第 iii 组里选择 iii 还是 i+ni+ni+n，其在对 nnn 取模意义下都相当于是增加了 iii。而 ∑i=0n−1i=n(n−1)2=n2−n2≢0(modn)\sum\limits_{i=0}^{n-1}i=\frac{n(n-1)}2=\frac{n^2-n}2\not\equiv 0\pmod ni=0∑n−1 i=2n(n−1) =2n2−n ≡0(modn)，因此模 2n2n2n 显然也无法整除，也就是无论后手怎么操作，先手都是必胜。 2∤N2\NMID N2∤N 可能是一个不太一样的角度？考虑到 2n2n2n 个数中  mod  n\bmod\ nmod n 值为 0,1,2,…,n−10,1,2,\ldots,n-10,1,2,…,n−1 的数都恰好有 222 个，因此一旦后手存在一种方案恰好选取了  mod  n\bmod\ nmod n 值为 0,1,2,…,n−10,1,2,\ldots,n-10,1,2,…,n−1 的数各一个，则这些数的和  mod  n\bmod\ nmod n 一定为 000。又因为此时所有数的和  mod  2n\bmod\ 2nmod 2n 的值一定为 nnn，因此若这样的方案  mod  2n\bmod\ 2nmod 2n 的值为 nnn，则选剩下所有没被选的数即可使得和  mod  2n\bmod\ 2nmod 2n 的值为 000。 然后考虑证明无论先手怎么给元素分组，后手都可以给出一个这样的策略： 设当前组两个元素的值为 (i,j)(i,j)(i,j)，则： * 若 i≡j(modn)i\equiv j\pmod ni≡j(modn)，则选哪一个元素都不会影响  mod  n\bmod\ nmod n 的值，直接忽略。 * 否则，给每一组的元素  mod  n\bmod\ nmod n 的值之间连一条边，则图一定由若干个不相交的简单环组成。考虑找到连接 i mod ni\bmod nimodn 和 j mod nj\bmod njmodn 两个元素的值，则顺着这个环绕一圈每一次选择相同方向的端点一定能恰好取遍环上所有  mod  n\bmod\ nmod n 的值。 因此可以证明此时后手一定存在一组恰好取完值  mod  n\bmod\ nmod n 后为 0,1,2,…,n−10,1,2,\ldots,n-10,1,2,…,n−1 的方案，此时后手一定可以胜利。 027. CF850D TOURNAMENT CONSTRUCTION（*2800\COLOR{RED}28002800） 感觉知道 Landau 定理之后就很简单（） 前置知识 Landau 定理：一个长度为 nnn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 是竞赛图每点出度从小到大排列的序列，当且仅当下面两个条件同时满足： * ∑i=1nai=n(n−1)2\sum\limits_{i=1}^n a_i=\frac{n(n-1)}2i=1∑n ai =2n(n−1) * ∑i=1jai≥j(j−1)2\sum\limits_{i=1}^j a_i\ge\frac{j(j-1)}2i=1∑j ai ≥2j(j−1) （1≤j≤n1\le j\le n1≤j≤n） 题解 对 nnn 个点的竞赛图，记 deg⁡i\deg_idegi 表示 iii 点的出度大小，则图上边的数量即为 ∑i=1ndeg⁡i=n(n−1)2\sum\limits_{i=1}^n\deg_i=\frac{n(n-1)}2i=1∑n degi =2n(n−1) 。因为题目的数据范围中保证了图上边的总数量不超过 30n30n30n，解不等式可得 n≤61n\le 61n≤61 一定可以满足条件。 因此考虑直接 dp：设 fi,j,kf_{i,j,k}fi,j,k 表示当前处理到了 iii 号点，当前点的数量为 jjj，边的数量为 kkk，是否合法。转移直接枚举 iii 号点增加的边的数量即可，构造方案在 dp 过程中记录转移路径然后利用 Landau 定理随便构造即可。 总时间复杂度为 O(n5)O(n^5)O(n5)，但是跑不满所以可以通过。 028. P15555 [CCPC 2025 哈尔滨站] 比赛（*34003\COLOR{RED}{400}3400） 难度评的比较高主要是因为 KTT 这个 ds 太冷门了（）oi wiki 上甚至都没有介绍（） 很牛的题。这个 kkk 的限制看上去就很不舒服，考虑先处理 k=1k=1k=1 的情况。 此时 O(nq)O(nq)O(nq) 的暴力是容易的。考虑对每次询问直接暴力 dp 处理，dp 限制内部考虑贪心，显然对于位置 iii 而言，在保证合法的情况下 xix_ixi 的值越小越好。因此设 fif_ifi 表示当前处理了 Li∼iL_i\sim iLi ∼i 的人，xix_ixi 的值最小是多少。显然有初始条件 fLi=lLif_{L_i} = l_{L_i}fLi =lLi ，转移方程 fi=max⁡(fi−1+d,li)f_i=\max(f_{i-1}+d,l_i)fi =max(fi−1 +d,li )。此时合法的充要条件即为 ∀i∈[Li,Ri]∩N,fi≤ri\forall i\in[L_i,R_i]\cap\mathbb N,f_i\le r_i∀i∈[Li ,Ri ]∩N,fi ≤ri 。 因为每次询问会单独给出一个 ddd 所以上面的 dp 无法直接上 ddp 维护。因此考虑套路的展开 dp 方程式，得到：fi=max⁡j=Limax⁡(lj+d(i−j))f_i=\max\limits_{j=L}^i\max(l_j+d(i-j))fi =j=Lmaxi max(lj +d(i−j))，因此可行性条件可以看作是对每个 i∈[L,R]i\in[L,R]i∈[L,R] 都有 ∀j∈[L,i),lj+d(i−j)≤rj\forall j\in[L,i),l_j+d(i-j)\le r_j∀j∈[L,i),lj +d(i−j)≤rj ，移项可得有 max⁡j=Li−1(lj+d(i−j)−rj)≤0\max\limits_{j=L}^{i-1}(l_j+d(i-j)-r_j)\le 0j=Lmaxi−1 (lj +d(i−j)−rj )≤0，套路的分离参数把 i,ji,ji,j 的项分开考虑得到 max⁡j=Li−1[(lj−jd)−(ri−id)]≤0\max\limits_{j=L}^{i-1}[(l_j-jd)-(r_i-id)]\le 0j=Lmaxi−1 [(lj −jd)−(ri −id)]≤0。为了让里面这个东西的值最大，容易想到在左侧取一个 jjj 满足 lj−jdl_j-jdlj −jd 的值最大，右侧取一个 iii 满足 ri−idr_i-idri −id 的值最小（显然需要满足 L≤j<i≤RL\le j<i\le RL≤j<i≤R）。 考虑用一个黑盒 ds 来维护上面的信息，在该黑盒的每个结点上维护信息 mxmxmx 表示在该区间上的所有 iii 中 li−idl_i-idli −id 的最大值，mimimi 表示在该区间上的所有 iii 中 ri−idr_i-idri −id 的最小值，dfdfdf 表示在该区间上所有 iii 的 (lj−jd)−(ri−id)(l_j-jd)-(r_i-id)(lj −jd)−(ri −id) 的最大值。先不管这个 ddd 怎么处理考虑先合并信息，那么假设此时要合并的结点左右儿子分别为 L,RL,RL,R 两个结点，mx,mimx,mimx,mi 是容易的直接取对应的 max⁡\maxmax / min⁡\minmin 值即可，而 dfdfdf 则可以直接从左右儿子继承，或在 LLL 中取 max⁡\maxmax，在 RRR 中取 min⁡\minmin，即：df=max⁡(L.df,R.df,L.mx−R.mi)df=\max(L.df,R.df,L.mx-R.mi)df=max(L.df,R.df,L.mx−R.mi)。 此时考虑 ddd 的信息怎么处理，这个东西可以看作是每次操作会先对区间的 iii 位置值对应增加 ididid，操作结束时刻对区间的 iii 位置值对应减少 ididid，也就是每次区间加 / 减一个一次函数。注意到一次操作内只有给定的询问区间 [L,R][L,R][L,R] 内的数才会被考虑到其余的数都不会被考虑到，因此直接把区间加减一次函数看作是对整体做操作。然后考虑到问题没有强制在线因此考虑 P5073 的套路把所有的 ddd 离线下来从小到大排序，此时相邻两次 ddd 的询问可以看作是整体加斜率为两个 ddd 的差（这个值一定 ≥0\ge 0≥0）截距为 000 的一次函数，因此直接上 KTT 大力维护即可（注：为了保持 KTT 的结构这里需要把最小值取反，维护最小值相反数的最大值）。 然后容易发现 kkk 这个信息是好处理的，很显然把 Li,Li+1,…,RiL_i,L_i+1,\ldots,R_iLi ,Li +1,…,Ri 这些人按顺序依次分配到 1,2,3,…,k,1,2,3,…,k,1,…1,2,3,\ldots,k,1,2,3,\ldots,k,1,\ldots1,2,3,…,k,1,2,3,…,k,1,… 队内就一定是最优的，证明简单调整法即可。 总时间复杂度为 O(nklog⁡3n)O(nk\log^3n)O(nklog3n) 瓶颈在于维护 KTT。但是众所周知 KTT 十分跑不满，实际运行下来也就 O(nklog⁡2n)O(nk\log^2n)O(nklog2n) 级别，因此可以通过该题。 2026.03.21 前路漫漫 总有绕不过的弯 人生太短 悲欢自渡皆是伤 这熙攘的人潮 谁不迷惘 谁不是 在崩溃的边缘 苦求着希望 想要用魔法 解开生活的惆怅 谁不是奔跑在黑暗中 追寻微弱的光 也曾轻言过失败 也曾被冷眼相待 在最平庸的日子里 频繁受伤害 （王小帅 天真的橡皮） 029. P15502 [ICPC 2025 APC] BOOK SORTING（*2900\COLOR{RED}{2900}2900） 容易证明一定存在一个最优形态，满足存在两个位置 1≤l≤r≤n1\le l\le r\le n1≤l≤r≤n，使得执行的操作形如： * 把 l−1,l−2,…,1l-1,l-2,\ldots,1l−1,l−2,…,1 这些书按顺序移动到最左侧。 * 把 r+1,r+2,…,nr+1,r+2,\ldots,nr+1,r+2,…,n 这些书按顺序移动到最右侧。 * l∼rl\sim rl∼r 范围内的书全部相邻项交换排序。 因此贡献即为：n−1−(r−l)+inv(al,al+1,…,ar)n-1-(r-l)+\text{inv}(a_l,a_{l+1},\ldots,a_r)n−1−(r−l)+inv(al ,al+1 ,…,ar ) 也就是最大化 (r−l)−inv(al,al+1,…,ar)(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)(r−l)−inv(al ,al+1 ,…,ar ) 的值，其中 inv(seq)\text{inv}(seq)inv(seq) 表示 seqseqseq 序列的逆序对的数量。 （注：这里的 aaa 是 ppp 的逆排列，即 api=ia_{p_i}=iapi =i）。 考虑固定右端点 rrr，记 SrS_rSr 集合内存储了所有左端点 lll 满足 1≤l≤r1\le l\le r1≤l≤r 且对于所有位置 j∈(l,r]j\in(l,r]j∈(l,r]，都有 (r−l)−inv(al,al+1,…,ar)>(r−j)−inv(aj,aj+1,…,ar)(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)>(r-j)-\text{inv}(a_j,a_{j+1},\ldots,a_r)(r−l)−inv(al ,al+1 ,…,ar )>(r−j)−inv(aj ,aj+1 ,…,ar )。 此时把 SrS_rSr 按照左端点 lll 的位置从大到小排序（下标从 111 开始），则有一个关键结论：(r−Sr,j)−inv(aSr,j,aSr,j+1,…,ar)=j−1(r-S_{r,j})-\text{inv}(a_{S_{r,j}},a_{S_{r,j}+1},\ldots,a_r)=j-1(r−Sr,j )−inv(aSr,j ,aSr,j +1 ,…,ar )=j−1。为了方便，后面记 (r−l)−inv(al,al+1,…,ar)(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)(r−l)−inv(al ,al+1 ,…,ar ) 的值为 f(l,r)f(l,r)f(l,r)。下面给出该结论的证明： :::success[证明] 要证明的结论为：f(Sr,j,r)=j−1f(S_{r,j},r)=j-1f(Sr,j ,r)=j−1。 套路的考虑对临项做差，得到 f(i,r)−f(i+1,r)=1−gif(i,r)-f(i+1,r)=1-g_if(i,r)−f(i+1,r)=1−gi ，其中 gig_igi 的值为 [i+1,r][i+1,r][i+1,r] 中比 aia_iai 小的元素的数量。因为 gi≥0g_i\ge 0gi ≥0 所以显然有 f(i,r)≤f(i+1,r)+1f(i,r)\le f(i+1,r)+1f(i,r)≤f(i+1,r)+1。 因为 Sr,∗S_{r,*}Sr,∗ 集合内只有对应 fff 值严格变大的位置，因此一定有 f(Sr,j,r)=f(Sr,j−1,r)+1f(S_{r,j},r)=f(S_{r,j-1},r)+1f(Sr,j ,r)=f(Sr,j−1 ,r)+1。而又因为有 f(Sr,1=r,r)=0f(S_{r,1}=r,r)=0f(Sr,1 =r,r)=0，因此 f(Sr,j,r)=j−1f(S_{r,j},r)=j-1f(Sr,j ,r)=j−1，命题得证。 ::: 因此最大化 (r−l)−inv(al,al+1,…ar)(r-l)-\text{inv}(a_l,a_{l+1},\ldots a_r)(r−l)−inv(al ,al+1 ,…ar ) 即 f(l,r)f(l,r)f(l,r) 的最大值其实就是 max⁡1≤r≤n(∣Sr∣−1)\max\limits_{1\le r\le n}(|S_r|-1)1≤r≤nmax (∣Sr ∣−1)，因此只需要对每个右端点 rrr 求出 ∣Sr∣|S_r|∣Sr ∣ 的值即可。 直接求 SrS_rSr 是困难的，因此可以想到通过 SrS_rSr 递推出 Sr+1S_{r+1}Sr+1 。显然此时有 f(r+1,r+1)=0f(r+1,r+1)=0f(r+1,r+1)=0。若不考虑逆序对的影响则有 f(l,r+1)=f(l,r)+1f(l,r+1)=f(l,r)+1f(l,r+1)=f(l,r)+1，但是若有 al>ar+1a_l>a_{r+1}al >ar+1 则 f(1,r+1),f(2,r+1),…,f(l,r+1)f(1,r+1),f(2,r+1),\ldots,f(l,r+1)f(1,r+1),f(2,r+1),…,f(l,r+1) 都会受到这组逆序对的影响，导致这些 fff 值全部减去 111。 考虑维护该事件对 Sr+1S_{r+1}Sr+1 的影响。因为在考虑逆序对影响之前有 f(Sr,j)=j−1f(S_{r,j})=j-1f(Sr,j )=j−1，现在对左端点 p∈[1,l]p\in[1,l]p∈[1,l] 的 ppp 对应的 fff 值减少 111，找出最大的位置 qqq 满足 qqq 是集合中最大的满足 Sr,q≤lS_{r,q}\le lSr,q ≤l 的位置，则此时 Sr,1,Sr,2,…,Sr,q−1S_{r,1},S_{r,2},\ldots,S_{r,q-1}Sr,1 ,Sr,2 ,…,Sr,q−1 对应的 fff 值不会变化，Sr,q,Sr,q+1,…S_{r,q},S_{r,q+1},\ldotsSr,q ,Sr,q+1 ,… 对应的 fff 值都会减少 111。因此此时只有 Sr,qS_{r,q}Sr,q 一个位置对应的 fff 值不再是前缀 max⁡\maxmax 位置，在集合中二分出这个位置并将其删除即可。 容易想到用 set 来维护这个结构，每次从 SrS_rSr 扩展到 Sr+1S_{r+1}Sr+1 只需要先在集合加入 f(r+1,r+1)f(r+1,r+1)f(r+1,r+1) 的影响，然后再二分出 qqq 的位置并将 Sr,qS_{r,q}Sr,q 从集合中删除。显然该算法流程的时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)，可以通过该题。 030. [ABC450G] RANDOM SUBTRACTION（*2400\COLOR{PINK}{2400}2400） 可以证明，n>2n>2n>2 时答案一定只和 ∑i=1nai,∑i=1nai2\sum\limits_{i=1}^na_i,\sum\limits_{i=1}^na_i^2i=1∑n ai ,i=1∑n ai2 有关。下面给出上述结论的证明： ::::success[证明]{open} :::success[结论]{open} E[x2]E[x^2]E[x2] 一定是关于 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 的二次式。 ::: :::success[证明] 操作形如选择两个数 a,ba,ba,b，把这两个数删除然后再加入 a−ba-ba−b 这个元素。因为这是一个线性操作，因此 xxx 一定是 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 的一个线性组合。 因此 x2x^2x2 是关于 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 的二次式，根据期望的线性性可知 E[x2]E[x^2]E[x2] 同样也是二次式。 ::: 因此考虑把 E[x2]E[x^2]E[x2] 用二次式的形式表示出来，即 ∑i=1nαiAi2+∑i=1n∑j=1n[i≠j]βi,jAiAj\sum\limits_{i=1}^n\alpha_iA_i^2+\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i\neq j]\beta_{i,j}A_iA_ji=1∑n αi Ai2 +i=1∑n j=1∑n [i=j]βi,j Ai Aj 。 但是注意到 E[x2]E[x^2]E[x2] 的值不能因为交换 AAA 数组中的两个位置就导致其值发生变化，因此必须有：α1=α2=…=αn,β1,2=β1,3=β1,4=…=βn,n−1\alpha_1=\alpha_2=\ldots=\alpha_n,\beta_{1,2}=\beta_{1,3}=\beta_{1,4}=\ldots=\beta_{n,n-1}α1 =α2 =…=αn ,β1,2 =β1,3 =β1,4 =…=βn,n−1 。也即 E[x2]E[x^2]E[x2] 可以表示为 α∑i=1nAi2+β∑i=1n∑j=1n[i≠j]AiAj\alpha\sum\limits_{i=1}^nA_i^2+\beta\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i\neq j]A_iA_jαi=1∑n Ai2 +βi=1∑n j=1∑n [i=j]Ai Aj 。 此时记 s1=∑i=1nAi,s2=∑i=1nAi2s_1=\sum\limits_{i=1}^nA_i,s_2=\sum\limits_{i=1}^nA_i^2s1 =i=1∑n Ai ,s2 =i=1∑n Ai2 ，把上式所有含 AAA 的项都用 s1,s2s_1,s_2s1 ,s2 表示，得到：E[x2]=αs2+β(s12−s2)E[x^2]=\alpha s_2+\beta(s_1^2-s_2)E[x2]=αs2 +β(s12 −s2 )。 :::: 此时可以直接写个暴力然后把 α,β\alpha,\betaα,β 的值打表求出来，下面给出一个正常推导的做法。 先给数组 AAA 代入特值，令 A1=A2=…=An−1=0,An=tA_1=A_2=\ldots=A_{n-1}=0,A_n=tA1 =A2 =…=An−1 =0,An =t，则显然有 E[x2]=t2,s1=t,s2=t2E[x^2]=t^2,s_1=t,s_2=t^2E[x2]=t2,s1 =t,s2 =t2，代入前面给出的式子得到 E[x2]=t2=αt2E[x^2]=t^2=\alpha t^2E[x2]=t2=αt2，因此必然有 α=1\alpha=1α=1。 考虑记 bib_ibi 表示 n=in=in=i 时上式 β\betaβ 的值，则 E[x2]=s2+bn(s12−s2)E[x^2]=s_2+b_n(s_1^2-s_2)E[x2]=s2 +bn (s12 −s2 )。此时考虑若在某次操作中选择了 i,ji,ji,j 两个位置，s2s_2s2 的值会减少 2AiAj2A_iA_j2Ai Aj 。因为 E[AiAj]=s12−s2n(n−1)E[A_iA_j]=\frac{s_1^2-s_2}{n(n-1)}E[Ai Aj ]=n(n−1)s12 −s2 ，所以有 E[s2]=s2−2(s12−s2)n(n−1)E[s_2]=s_2-\frac{2(s_1^2-s_2)}{n(n-1)}E[s2 ]=s2 −n(n−1)2(s12 −s2 ) 。 s12−s2s_1^2-s_2s12 −s2 的值会增加 2AiAj+4Aj2−4Ajs12A_iA_j+4A_j^2-4A_js_12Ai Aj +4Aj2 −4Aj s1 ，对其每项分别计算期望，得到：E[Aj]=s1n,E[Aj2]=s2n,E[AiAj]=s12−s2n(n−1)E[A_j]=\frac{s_1}n,E[A_j^2]=\frac{s_2}n,E[A_iA_j]=\frac{s_1^2-s_2}{n(n-1)}E[Aj ]=ns1 ,E[Aj2 ]=ns2 ,E[Ai Aj ]=n(n−1)s12 −s2 ，因此有 E[s12−s2]=s12−s2−4s1×s1n+4×s2n+2(s12−s2)n(n−1)E[s_1^2-s_2]=s_1^2-s_2-4s_1\times\frac{s_1}n+4\times\frac{s_2}n+\frac{2(s_1^2-s_2)}{n(n-1)}E[s12 −s2 ]=s12 −s2 −4s1 ×ns1 +4×ns2 +n(n−1)2(s12 −s2 ) ，化简可得 E[s12−s2]=(n−2)(n−3)(s12−s2)n(n−1)E[s_1^2-s_2]=\frac{(n-2)(n-3)(s_1^2-s_2)}{n(n-1)}E[s12 −s2 ]=n(n−1)(n−2)(n−3)(s12 −s2 ) 。 记 fn(A)f_n(A)fn (A) 为长度为 nnn 的 AAA 序列最后得到 x2x^2x2 的期望值，则有 f1(A)=A12,f2(A)=(A1−A2)2,fn(A)=E[fn−1(A′)]f_1(A)=A_1^2,f_2(A)=(A_1-A_2)^2,f_n(A)=E[f_{n-1}(A')]f1 (A)=A12 ,f2 (A)=(A1 −A2 )2,fn (A)=E[fn−1 (A′)]，其中 A′A'A′ 是 AAA 序列进行一次操作后得到的序列，把 E[x2]E[x^2]E[x2] 代入上式可得 fn(A)=E[s2+bn−1(s12−s2)]=s2−2(s12−s2)n(n−1)+bn−1(n−2)(n−3)(s12−s2)n(n−1)f_n(A)=E[s_2+b_{n-1}(s_1^2-s_2)]=s_2-\frac{2(s_1^2-s_2)}{n(n-1)}+b_{n-1}\frac{(n-2)(n-3)(s_1^2-s_2)}{n(n-1)}fn (A)=E[s2 +bn−1 (s12 −s2 )]=s2 −n(n−1)2(s12 −s2 ) +bn−1 n(n−1)(n−2)(n−3)(s12 −s2 ) 。又因为 fn(A)=s2+bn(s12−s2)f_n(A)=s_2+b_n(s_1^2-s_2)fn (A)=s2 +bn (s12 −s2 )，联立两个 fn(A)f_n(A)fn (A) 的关系式可得 bn=−2n(n−1)+(n−2)(n−3)bn−1n(n−1)b_n=-\frac2{n(n-1)}+\frac{(n-2)(n-3)b_{n-1}}{n(n-1)}bn =−n(n−1)2 +n(n−1)(n−2)(n−3)bn−1 。线性求出前缀的逆元然后模拟上述过程可以做到 O(n)O(n)O(n) 求解答案。 :::success[能不能 O(1)O(1)O(1) 求出 bnb_nbn 的值？] 先观察样例可以发现答案形如 23\frac2332 加上一个数，然后再结合暴力打表，可以猜想 n≥3n\ge 3n≥3 时有 bn=−23(n−1)b_n=-\frac2{3(n-1)}bn =−3(n−1)2 ，然后简单数学归纳证明即可。 ::: :::warning[注意] 特判 n≤2n\le 2n≤2 的时候一定要记得给答案平方！！！ ::: 2026.03.22 那时候手心余温刚好 晚风很温柔有你陪就足够 时间是个小偷 无情盗走你我之间的所有 未留温暖又平凡的以后 你说分开也能相守 不过一个人把回忆保留 却还记得你的笑容 （yihuik苡慧 银河与星斗） 031. CF1579G MINIMAL COVERAGE（*2100\COLOR{ORANGE}{2100}2100） 有两个端点比较难受，所以考虑转化问题，找到最小的 mmm 使得存在一个起点 t∈[0,m]t\in [0,m]t∈[0,m] 使得每一步 +ai+a_i+ai 或 p−aip-a_ip−ai 后值都在 [0,m][0,m][0,m] 范围内。 显然 mmm 是有单调性的，所以考虑二分 mmm 的值，判定是否合法容易简单想到 O(nm)O(nm)O(nm) 暴力背包 dp。此时总时间复杂度为 O(nVlog⁡V)O(nV\log V)O(nVlogV)，其中 V=∑i=1nai=O(n2)V=\sum\limits_{i=1}^n a_i=O(n^2)V=i=1∑n ai =O(n2)，即总时间复杂度为 O(n3log⁡n)O(n^3\log n)O(n3logn)。 考虑优化。容易发现 dp 转移的形式就是对一个 010101 序列整体左移整体右移然后再按位与把序列框在 [0,m][0,m][0,m] 范围内。因此容易想到用 bitset 简单优化做到 O(n3log⁡nω)O(\frac{n^3\log n}\omega)O(ωn3logn ) 求解。 但是这个时候还是过不去。考虑进一步优化，注意到答案的上界不会超过 2max⁡ai2\max a_i2maxai 。证明的话考虑若一个数大于 max⁡ai\max a_imaxai 那么下一个直接减 aia_iai 一定不会使得上界超过 2max⁡ai2\max a_i2maxai 。把二分的上界改设为 2max⁡ai2\max a_i2maxai 可以做到总时间复杂度 O(n2log⁡nω)O(\frac{n^2\log n}\omega)O(ωn2logn ) 可以通过该题。 032. CF1768E PARTIAL SORTING（*2300\COLOR{YELLOW}{2300}2300） 感觉比较像 sale（？但是要简单一些 可以证明对于任意一个排列都最多只需要三次操作使得排列变得满足条件。因此考虑分别计数需要 0,1,2,30,1,2,30,1,2,3 次操作可以排序的排列数量： * 需要 000 次操作的排列数量：显然答案就是 111。 * 需要 111 次操作的排列数量：显然这次操作只能把前 2n2n2n 个数排序或把后 2n2n2n 个数排序，因此需要不超过 111 次操作的排列数量可以被表示为前 nnn 个数正好是 1,2,3,…,n1,2,3,\ldots,n1,2,3,…,n 或后 nnn 个数正好是 2n+1,2n+2,…,3n2n+1,2n+2,\ldots,3n2n+1,2n+2,…,3n 的排列数量，简单容斥可得答案为 2(2n)!−n!2(2n)!-n!2(2n)!−n!。 * 需要 222 次操作的排列数量：显然此时排列要么 1∼n1\sim n1∼n 元素在前 2n2n2n 个位置，要么 2n∗∗∗∗im3n2n****im 3n2n∗∗∗∗im3n 元素在后 2n2n2n 个位置。对于需要不超过 222 次操作的排列数量，若假设两个条件互斥，则显然答案可以被计数为 2(2n)!n!(2nn)2(2n)!n!\binom{2n}n2(2n)!n!(n2n )。然后考虑容斥，计数同时满足前面给出的两个条件的排列数目。容易想到枚举出现在中间区间里数的情况。这里枚举 iii 表示恰好有 iii 个数值在 [n+1,2n][n+1,2n][n+1,2n] 范围内出现在序列的前 nnn 个位置。那么可以这样计数： * 前 nnn 个位置里有 iii 个数字在 [1,n][1,n][1,n] 范围内，方案数是 n!(ni)n!\binom nin!(in )。 * 中 nnn 个位置里有 n−in-in−i 个数在 [1,n][1,n][1,n] 范围内，方案数是 n!(ni)n!\binom nin!(in )。 * 后 nnn 个位置里有 iii 个数在 [n+1,3n][n+1,3n][n+1,3n] 范围内，方案数是 n!(2n−in)n!\binom{2n-i}nn!(n2n−i )。 * 直接乘法原理乘起来计数即可。 * 需要 333 次操作的排列数量：直接用排列数量 (3n)!(3n)!(3n)! 减去需要 0,1,20,1,20,1,2 次操作的排列数量即可。 该算法总时间复杂度为 O(n)O(n)O(n)，可以通过该题。 2026.03.23 世界赠予我虫鸣 也赠予我雷霆 赠我弯弯一枚月 也赠予我晚星 赠我一场病 又慢慢痊愈摇风铃 赠我一场空 又渐渐填满真感情 （王菲 世界赠予我的） 033. AT_ARC122_D [ARC122D] XOR GAME（*2400\COLOR{PINK}{2400}2400） 感觉是比较套路的题？注意到问题可以转化为把 2n2n2n 个数分成 nnn 个二元组，使得每个二元组内两个数的异或的最大值最小。套路的从二进制的高位开始向低位考虑： * 若当前位上有偶数个数二进制表示为 111，则显然可以贪心的两两分组使得 111 和 111 分组 000 和 000 分组，因此直接按二进制 0,10,10,1 分为两组然后分别递归处理即可。 * 若当前位上有奇数个数二进制表示为 111，则必然需要找恰好一组数使得其中一个数二进制表示为 111，另一个数二进制表示为 000。直接贪心的找出一组异或最小的数，可以证明这个贪心策略正确。用 01-Trie 维护信息，时间复杂度为 O(nlog⁡V)O(n\log V)O(nlogV) 可以通过该题。 034. P6009 [USACO20JAN] NON-DECREASING SUBSEQUENCES P（*2600\COLOR{RED}{2600}2600） 【模板】猫树分治。对于当前的分治区间 [l,r][l,r][l,r] 而言： * 若 l=rl=rl=r，则直接处理即可。 * 否则，记区间的中点为 MMM，则先分别递归处理 [l,M][l,M][l,M] 和 [M+1,r][M+1,r][M+1,r] 两个区间内的答案，然后套路的记 fi,jf_{i,j}fi,j 表示 [i,M][i,M][i,M] 区间内最后一个元素是 jjj 的不下降子序列的数量，gi,pg_{i,p}gi,p 表示 [M+1,i][M+1,i][M+1,i] 区间内第一个元素是 ppp 的不下降子序列的数量，转移直接枚举 j,pj,pj,p 然后合并 f,gf,gf,g 两个数组的 dp 信息即可。 总时间复杂度为 O(nk2log⁡n)O(nk^2\log n)O(nk2logn)，可以通过该题。 2026.03.24 Ho baby 情话多说一点 想我就多看一眼 表现多一点点 让我能真的看见 Oh bye 少说一点 想陪你不只一天 多一点 让我心甘情愿 爱你[比心] （王心凌 爱你） 035. WIKIPEDIA（*2600\COLOR{RED}{2600}2600） 考虑套路的转化可行条件。容易发现题目给出的条件等价于：一个序列 qqq 是合法的当且仅当删除 qqq 序列的 nnn 后得到的序列 ttt 从后往前操作可以把升序排列变为 ppp。因此答案就是 nnn 乘以能够得到排列 ppp 的序列 ttt 的数量。 更确切的说：记 sis_isi 表示当前操作交换 ai,ai+1a_i,a_{i+1}ai ,ai+1 两个数，则对于长度为 n−1n-1n−1 的排列 ttt，操作过程可以看作是：从排列 1,2,3,…,n1,2,3,\ldots,n1,2,3,…,n 开始按顺序执行操作 st1,st2,…,stn−1s_{t_1},s_{t_2},\ldots,s_{t_n-1}st1 ,st2 ,…,stn −1 并最终得到 ppp 排列。最后答案额外乘以 nnn。 注意到若 ∣i−j∣>1|i-j|>1∣i−j∣>1，则 sis_isi 和 sjs_jsj 两个操作调换顺序不会影响最后得到的排列。考虑记 did_idi ：若 di=1d_i=1di =1 则表示 iii 在 ttt 中出现在 i+1i+1i+1 的前面，否则（di=0d_i=0di =0）表示 iii 在 ttt 中出现在 i+1i+1i+1 的后面。此时考虑把 1,2,3,…,n−11,2,3,\ldots,n-11,2,3,…,n−1 看作是图上的若干结点，则若 di=1d_i=1di =1 则连一条 i→i+1i\to i+1i→i+1 的边，否则连一条 i+1→ii+1\to ii+1→i 的边。则此时 ttt 正好是这张有向图的一个拓扑序。 记 S1,S2S_1,S_2S1 ,S2 两个集合为：S1={i+1∣di=1},S2={i+1∣di=0}S_1=\lbrace i+1\mid d_i=1\rbrace,S_2=\lbrace i+1\mid d_i=0\rbraceS1 ={i+1∣di =1},S2 ={i+1∣di =0}。则最终得到的置换 ppp 一定存在一个循环分解形如 1,S1,n,S21,S_1,n,S_21,S1 ,n,S2 的形式，且 S1S_1S1 一定是升序排列的，S2S_2S2 一定是降序排列的。 此时套路的记 π\piπ 为 ttt 的逆排列，则 ddd 的限制条件形如： * di=1d_i=1di =1：πi<πi+1\pi_i<\pi_{i+1}πi <πi+1 * di=0d_i=0di =0：πi>πi+1\pi_i>\pi_{i+1}πi >πi+1 问题变为计数有多少个长度为 n−1n-1n−1 的排列满足上述 ddd 对 π\piπ 的限制。因此考虑套路的 dp：设 fi,jf_{i,j}fi,j 表示当前处理了排列的前 iii 个元素，满足 ddd 的前 i−1i-1i−1 个限制，且最后一个数是这 iii 个数里第 jjj 小的元素。则转移枚举下一个数的排名可以做到 O(n3)O(n^3)O(n3)。注意到转移的是一段连续的区间因此使用前缀和维护，时间复杂度优化到 O(n2)O(n^2)O(n2) 可以通过该题。 036. AT_AGC071_C [AGC071C] ORIENTABLE AS DESIRED（*32003\COLOR{RED}{200}3200） :::info[结论 111] 若无向图 GGG 是一棵树，则一定不存在这样的一个数组 XXX 满足题目中给出的条件。 ::: :::warning[提示 111] 试着给树定根，然后自底向上递归处理度数信息？ ::: ::::success[证明结论 111] 考虑先给树随便定一个根。此时很显然叶子结点可以满足条件。 :::info[结论 1.11.11.1] 翻转一个结点 uuu 子树内所有边以及 uuu 和其父结点的边的方向不会影响 uuu 子树内除 uuu 结点以外的所有点的合法性。 ::: :::warning[提示 1.11.11.1] 考虑 uuu 子树内的结点入度和出度会怎么变化？ ::: :::success[证明 1.11.11.1] 翻转一个结点 uuu 子树内所有的边后，对于 uuu 子树内一点 vvv，若满足 v≠uv\neq uv=u 则 vvv 点操作前后一定是恰好交换了入度和出度的值。 ::: 而对于非叶子结点的限制，考虑先递归处理其所有子结点 vvv 的子树条件，使得对于所有 vvv 都是满足条件的。 考虑先给每个子结点 vvv 的子树以及 u←vu\leftarrow vu←v 的边随便定向使得 vvv 子树内所有结点的信息都是合法的。此时若 uuu 结点不合法，根据结论 1.11.11.1 可知此时翻转 vvv 子树内所有的边以及 u←vu\leftarrow vu←v 的边不会导致 vvv 子树内任意一个点不再满足度数条件，而这样会导致 uuu 的入度和出度发生 ±1\pm 1±1 或 ∓1\mp 1∓1 的变化。容易发现必然存在一个调整方案使得 uuu 满足其度数条件。 :::: :::info[结论 222] 若图 GGG 不是二分图，则必然存在一个数组 XXX 满足题目给出的条件。 ::: :::warning[提示 222] 试着构造一个特殊的 XXX 数组？ ::: :::success[证明结论 222] 构造 X1=X2=…=Xn=0X_1=X_2=\ldots=X_n=0X1 =X2 =…=Xn =0。则此时要求一个点的入度或出度中至少有一个为 000。 也就是对于一个结点 uuu，要么和其相邻的边全都是从 uuu 出发的，要么和其相邻的边全都是到达 uuu 的。 考虑按照这个条件把所有点 uuu 分为两类点：若 uuu 点相邻的所有边均从 uuu 出发，则称其为 111 类点，否则称其为 222 类点。 则根据两类点的定义可知，一条边定向后只可以是从 111 类点连向 222 类点的边，即在原图上只能存在连接111 类点和 222 类点的边，不能存在一条边连接的两个点类别相同。因此若要存在一个定向方案满足条件，则图必须是一张二分图。 因此对非二分图，构造 X1=0,X2=0,…,Xn=0X_1=0,X_2=0,\ldots,X_n=0X1 =0,X2 =0,…,Xn =0 就一定不满足题目中给出的度数条件。 ::: :::warning[提示 333] 是否只需要研究一类特殊的 XXX 数组就可以正确求解问题？ ::: :::info[结论 333] 只需要研究形如 Xi=k,Xj=0(∀j,j≠i)X_i=k,X_j=0(\forall j,j\neq i)Xi =k,Xj =0(∀j,j=i) 的数组 XXX 即可。 ::: :::::success[证明结论 333] 先考虑若一个序列 XXX 中只有一个位置 XiX_iXi 的值可以不为 000，定向后得到的有向图会形如什么样。容易想到这张图除了 iii 结点以外，每个结点要么和其相邻的所有边都从她出发，要么和其相邻的所有点都连向她。 ::::warning[提示 3.13.13.1] 如果翻转树上两个点 u,vu,vu,v 的简单路径上所有边的方向，那么点度数的信息会发生怎样的变化？ :::: ::::success[提示 3.13.13.1 的答案] 容易发现若 uuu 到 vvv 路径上的点按照顺序可以写作为 u,x1,x2,…,xp,vu,x_1,x_2,\ldots,x_p,vu,x1 ,x2 ,…,xp ,v，则 x1,x2,…,xpx_1,x_2,\ldots,x_px1 ,x2 ,…,xp 点的入度和出度都不会发生变化。而 u,vu,vu,v 两点的入度要么增加 111 要么减少 111，出度则刚好相反。 :::: 考虑对于一个不合法的序列 XXX，记位置 v1,v2,…,vkv_1,v_2,\ldots,v_kv1 ,v2 ,…,vk 满足 Xvi≠0X_{v_i}\neq 0Xvi =0，则考虑每次选择两个非零点 vi,vjv_i,v_jvi ,vj 然后通过提示 3.13.13.1 中给出的操作把 viv_ivi 上度数不为 000 的部分转移到 vjv_jvj 上即可。且因为这个转移操作只需要把 i→ji\to ji→j 路径上所有边的方向翻转，因此设得到的新序列 YYY，则 XXX 不合法的充要条件即为 YYY 不合法，反之同理。 ::::: （这里只讨论 GGG 是二分图且不是树的情况）此时特判掉 XXX 序列全 000 的特殊情况，则对于给定的图 GGG，考虑固定 ppp 点，满足 Xp≠0X_p\neq 0Xp =0。此时考虑在图 GGG 中删除 ppp 点以及所有一端为 ppp 点的边，则此时： :::info[结论 444] 二分图删除一个结点和该结点相邻的边后，得到的新图仍然是一张二分图。 ::: :::info[结论 555] 若一张二分图中所有结点对应的 XXX 值都为 000，则确定一个点的入度为 000 / 出度为 000 后，一定可以确定整个连通块内每个点入度为 000 / 出度为 000。 ::: :::success[证明结论 555] 确定二分图连通块内一个点入度为 000 / 出度为 000 后，一定可以通过二分图染色的方式，使得同色的点一定同时满足入度为 000 / 出度为 000。而二分图染色确定一个点的颜色后一定可以唯一确定该点所在连通块内其余点的颜色。因此此时染色方案一定唯一，可以唯一确定。 ::: :::info[结论 666] ppp 点向同一个连通块内连的边的方向一定全部相同，即：要么全都是从 ppp 出发，要么全都是连向 ppp 点。 ::: :::success[证明结论 666] 考虑到二分图删掉若干点后仍然会得到一个二分图，而且二分图一定不存在任何奇环，而除了 ppp 点以外的所有点都要么全是从 ppp 出发的边，要么边全都连向 ppp 点。考虑到前面提到过二分图染色后颜色相同的点必须全都是从 ppp 点出发的边或者全都是连向 ppp 点的边，因此 ppp 点向同一个连通块内连的边的方向必然全都相同。 ::: 此时考虑记 ppp 点删除后各个连通块内和 ppp 点有边相连的点的数量分别为 a1,a2,…,ama_1,a_2,\ldots,a_ma1 ,a2 ,…,am ，则问题可以被转化为可重集合 {a1,a2,…,am}\lbrace a_1,a_2,\ldots,a_m\rbrace{a1 ,a2 ,…,am } 中是否对于任意一个整数 v∈[0,∑ai]v\in[0,\sum a_i]v∈[0,∑ai ] 都存在一个子集 T⊆ST\subseteq ST⊆S 满足 ∑i∈Ti=v\sum\limits_{i\in T}i=vi∈T∑ i=v。此时考虑 P15253 Raining Mex 的经典结论： :::info[结论 777] 可重集合 {a1,a2,…,am}\lbrace a_1,a_2,\ldots,a_m\rbrace{a1 ,a2 ,…,am } 中对任意一个整数 v∈[0,∑ai]v\in[0,\sum a_i]v∈[0,∑ai ] 都存在一个子集 T⊆ST\subseteq ST⊆S 满足 ∑i∈Ti=v\sum\limits_{i\in T}i=vi∈T∑ i=v，当且仅当把 aaa 数组内元素升序排序后，对任意 iii 都有 ∑j=1i−1aj≥ai−1\sum\limits_{j=1}^{i-1}a_j\ge a_i-1j=1∑i−1 aj ≥ai −1。 ::: ::::success[证明结论 777] 首先把 aaa 数组内元素升序排序。此时考虑套路的数学归纳，若当前处理的一段前缀内元素恰好可以凑出 0∼x0\sim x0∼x 的值，当前要加入的元素值为 yyy，则：若 x≥y−1x\ge y-1x≥y−1，则很显然此时可以凑出的元素的值为 0∼x+y0\sim x+y0∼x+y，否则此时无法凑出值在 x∗∗∗∗imy−1x****im y-1x∗∗∗∗imy−1 的元素。但是为什么在某个时刻出现无法凑出的值，后面就再也无法凑出这些值了呢？ :::info[结论 7.17.17.1] 对于一个升序排列长度为 nnn 的数组 aaa，若在某个时刻能够凑出的值不是一段连续的区间，则在之后无论怎么插入元素都不会使得能凑出的值是一段连续的区间。 ::: :::success[证明结论 7.17.17.1] 考虑第一次出现不是一段连续区间前，能凑出值为 0∼x0\sim x0∼x 的元素，插入了元素 yyy，则必有 x<y−1x<y-1x<y−1。此时无法凑出值为 x+1x+1x+1 的元素。而在后面加入的所有元素其值都不会小于 yyy，更不会小于 x+1x+1x+1，自然也无法凑出值为 x+1x+1x+1 的元素。而显然能凑出元素的上界就是当前所有元素的和，而这个和显然是严格大于 x+1x+1x+1 的。 ::: 因此可以证明前面给出的条件就是充要条件。 :::: 于是得到了一个时间复杂度为 O(n2)O(n^2)O(n2) 的做法：特判掉二分图和树的情况，然后考虑枚举点 ppp 作为序列 XXX 中唯一的非零点，求出删除点 ppp 后每个连通块和点 ppp 有边相连的点的数量 aia_iai ，排序（这里排序可以使用桶排）后通过结论 777 判断点 ppp 是否合法即可。显然输出 No 当且仅当对于每个 p∈[1,n]p\in [1,n]p∈[1,n]，aia_iai 都可以凑出值在 0∼∑ai0\sim \sum a_i0∼∑ai 内的元素。 考虑进一步优化该算法的时间复杂度。考虑若一个点 ppp 不是原图的割点，则原图删掉点 ppp 和与其相邻的所有边后仍然得到一张二分图，且图仍然是连通的。此时 ppp 点相邻的所有点，每个点相邻的边的方向都必须是相同的，且做二分图染色后这些和 ppp 相邻的点的颜色必然是相同的，因此这些点和 ppp 点之间的边方向必须全部指向 ppp 或者全部从 ppp 出发，也就是此时因为 ap≠0a_p\neq 0ap =0 所以只能有 ap=deg⁡(p)a_p=\deg(p)ap =deg(p)，这个情况是平凡的，无需通过上面的方法讨论。因此直接在图上求出所有的割点然后把这些点依次设为 ppp 直接枚举和 ppp 点相邻的每条边即可。总时间复杂度为 O(n+mlog⁡m)O(n+m\log m)O(n+mlogm)，可以通过该题。

互动｜用一句话证明你是信奥人

用一句话证明你是信奥人 hi，AC狗友们，玩梗时间又到啦！ 只要一句话，让懂的人会心一笑，让不懂的人一脸懵——你就是本届“黑话王者”！ 规则简单到像A+B Problem 在评论区留下一句只有信奥人才懂的梗/黑话/日常—— 可以是你的“当前状态”： > “我命由我不由CE” > “提交10次，AC 0次，心态9次” 也可以是你的“刷题习惯”： > “看到WA第一反应不是‘哇’，是‘Wrong Answer’” > “做梦都在想怎么优化那个O(n²)的循环” …… 🎁 奖励 活动截止，评论区符合参与条件的留言点赞TOP5每人获得， 罐头 × 50； @༺ཌༀ我要上浙大ༀད༻，@盛翰祺（不加团），@༺དༀ༒神.末日审判者༒ༀཌ༻，@格赫罗斯，@奶牛大学招生办 随机抽取5人，每人获得 罐头 × 20 @priority_queue‮， @Shirleynie，@浩云，@༺ཌༀ死·神ༀད༻，@上海交通大学-章老师 ⏰ 时间 即日起至 2026年3月29日 23:59 📮 参与方式 直接在本帖评论区留言，坐等点赞收割！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💚 来吧，让我看看谁的“信奥含量”超标！ 往期互动

#创作计划#最小生成树的构造及应用

叠甲：没事干写一篇好玩，不喜勿喷，有问题欢迎指出，暂时已完结。 本文只讲KRUSKAL，我在VJUDGE拉了个比赛包含所有题目,A-R题为例题，S-Y为附加题。 前置知识：并查集，贪心，树的性质，请先行了解。 一、最小生成树的定义 > 生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树．也即在图的边集中选择 𝑛−1𝑛 −1n−1条，将所有顶点连通。我们定义无向连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。 > FromFromFrom oi-wiki 二、KRUSKAL算法模板 Kruskal算法是一种贪心算法，非常好写，算法的思想是由边权从小到大遍历，只要两个节点还未联通，就把它们连上。维护连通性的问题，套用单次合并O(log⁡n)O(\log n)O(logn) 或者 𝑂(α(𝑚))𝑂(\alpha(𝑚))O(α(m))的并查集即可。加上排序的O(mlog⁡m)O(m\log m)O(mlogm)，Kruskal算法的总复杂度为O(mlog⁡m+mlog⁡n)O(m \log m + m \log n)O(mlogm+mlogn)。 贴上模板代码（即A题代码） 三、例题 B 这就是最大生成树的模板，排序规则改掉就行了。 C 跑WWW遍最小生成树，注意在输入时给每条边加一个第几周开放的参数，跑最小生成树时检测边的开放时间是否小于等于当前时间即可，这样就不用每周都排序了。 D 假设能使用kkk个卫星设备，就相当于让kkk个点直接连通，在最小生成树中，一定会用k−1k-1k−1条边。那么最优方案就一定是把原图中最长的k−1k-1k−1条边的边权取消，只需输出最小生成树中第kkk长的边即可。 E 题目要求我们最大化任意两个部落之间的距离的最小值，实际上这个最小值就是在不同部落的任意两个居住点的最近距离。不难想到在部落内部尽量连较短的边，不让更短的边放在不同部落之间。因为要分为kkk个部落，因此只需要n−kn-kn−k条有用的边（遍历到这条边时两节点还未被联通的边）即可，所以直接输出第n−k+1n-k+1n−k+1条有用边的长度即可。（就是连结两个部落的边中最短的） F 构造为图论问题，快速幂预处理连边，没了。 G 在线算法不知道怎么办，考虑离线处理，把所有查询的边都放进去排序，跑最小生成树，跑的过程中如果是原本就有的边直接正常处理，如果是查询边，检测这条边是否有用（即两个点是否已联通），如果有用就把Yes放入答案，没有就放入No，注意查询之间相互独立，所以就算有用也千万不要加边。 H 直接连边O(n2)O(n^2)O(n2)指定炸，考虑删边，例如当xi≤xj≤xkx_i \leq x_j \leq x_kxi ≤xj ≤xk 时，只需要连接iii与jjj、jjj与kkk，而不需要连iii与kkk。那么我们按x,yx,yx,y分别排序后将相邻点连边即可。可以证明如果一条边是有效的，那么一定不会在按xxx排序和按yyy排序后都被鉴定为无效边。 I 就是求在不用第一条边的情况下，第一条边的两个点联通的最小边权。跑第2−m2-m2−m条边最小生成树过程中检测第一条边两个点的连通性即可，注意如果最终都无法联通,输出10910^9109。 J 首先买了第 III 样东西，再买第 JJJ样的情况显然可以看做一条边权为KI,JK_{I,J}KI,J 的边，那么直接买一样东西花费AAA元的情况怎么办呢？这时候就可以引入一个超级源点，即000号点，这样就可以把这种情况构造为一条从000联向任意一点的边权为AAA的边了。 K 和J题几乎一模一样，挖水井就是向超级源点建边，修筑水道就是普通连边。 L 不讲了，L≈\approx≈K，但是注意这是远古题目答案末尾一定要换行！！！我被这个坑了20分钟。 M 笑点解析： 感谢PPL友情出演 接近正解的错误方法PPL已经给我们介绍过了，就是建两个超级源点分别代表港口与机场，然后暴力跑Kruskal，但是这样有个问题：我们的目标不是让包括超级源点在内的所有点联通，只是1−n1-n1−n号点的联通，因此可能会出现无效连边（明明1−n1-n1−n号点已经联通了还非要去连接超级源点）。 那么怎么办呢？注意到超级源点可以用也可以不用，那么枚举这两个超级源点的使用情况跑4遍Kruskal即可，注意可以给每条边一个编号，说明它属于机场边，港口边还是道路边，这样就不需要每次枚举使用情况都排序了。 那么为什么J、K、L没有这个问题呢？因为J、K、L题都必须使用超级源点，但是这道题就不一样了。 N 先不考虑额外的MMM条边，只看如何最小化生成树的ax+aya_x+a_yax +ay 之和，显然最优方案是一个菊花图，即将所有边都直接连向axa_xax 最小的点。如果不考虑额外MMM条边时，一条边不在最小生成树内，那么再加入MMM条边后，也一定不需要考虑，所以只需要连上原始生成树的N−1N-1N−1条边和额外的MMM条边并跑Kruskal即可。 O 不讲了，O≈\approx≈K，建边的公式不同，改一下就行了。 P 看完前面的题，你会发现Road真不难 首先因为村庄数少，不难想到遍历所有村庄的修复状态跑2k2^k2k次最小生成树，时间复杂度O(2kmlogm)O(2^kmlogm)O(2kmlogm)，48pts48pts48pts，考虑优化。 根据N题的剪枝方法，在不考虑村庄的情况下不在最小生成树内的边，有了村庄就更不可能在最小生成树内了。那么就可以预处理跑一边Kruskal，将最小生成树内的边放入新的边集，可以大幅缩减边数(1.1×106→1.1×1051.1\times10^6\to1.1\times10^51.1×106→1.1×105)。 根据M题的方法对包含村庄边在内的所有边进行预编号和预排序，这样就不用排2k2^k2k次序了。 最终时间复杂度O(mlogm+2knklogn)O(mlogm+2^knklogn)O(mlogm+2knklogn)，也可以加上启发式合并O(mlogm+2knkα(n))O(mlogm+2^knk\alpha(n))O(mlogm+2knkα(n))。 Q 这道题需要用Kruskal重构树。具体来说和普通的Kruskal唯一有区别的一点是Kruskal重构树不是直接连边，而是创造一个虚拟节点（例如在这题就是载重限制），让两个点变成这个虚拟节点的左右儿子（后面其实就是拿虚拟点合并了，虚拟点中父亲的点权一定小于（经常是大于）儿子的点权）。这题我们是希望限重越大越好，所以是跑最大生成树。查询的时候就求两个查询点在重构树上的LCA（一般朴素倍增即可），输出这个虚拟点的权值即可,时间复杂度O(mlogm+(n+q)logn)O(mlogm+(n+q)logn)O(mlogm+(n+q)logn)。好了恭喜你学会了Kruskal重构树，赶紧去把巅峰赛#31T6秒了吧。 R 不讲了，R≈\approx≈Q，上题是最大生成树，这题是最小生成树，没了。 大家觉得我有必要写S-Y吗（实际上除了S我一道都不会）

官方题解 | 巅峰赛#32

巅峰赛32题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 返程拼车 普及- T2 星港远航 普及/提高- T3 霓虹线路 普及/提高- T4 雾港灯串 普及- T5 星灯选址 普及- T6 分裂晶体 提高+/省选- T1 返程拼车 题目大意 给定 nnn 个同学在数轴上的位置 xix_ixi ，每辆车最多载 222 人，且两人之间距离满足 ∣xi−xj∣≤D|x_i-x_j|\le D∣xi −xj ∣≤D 才能拼车。求最少需要多少辆车使所有同学都能回家。 题解思路 要让车辆数最少，就要让“拼车的对数”尽量多，因为每拼成一对就比两人各自打车少用一辆车。 把所有位置 xix_ixi 排序为 p1≤p2≤⋯≤pnp_1\le p_2\le \dots \le p_np1 ≤p2 ≤⋯≤pn 。在有序序列上从左到右扫描： * 如果 pi+1−pi≤Dp_{i+1}-p_i\le Dpi+1 −pi ≤D，就把这两位同学配成一对，然后跳过这两人； * 否则 pip_ipi 无法与任何更右侧的人拼车（更右只会更远），只能单独一辆车。 这是最大化不相交配对数的典型贪心：能配就立刻配相邻元素。设配对数为 pairs，答案为 cars=n−pairs.\text{cars}=n-\text{pairs}. cars=n−pairs. 复杂度：排序 O(nlog⁡n)O(n\log n)O(nlogn)，扫描 O(n)O(n)O(n)。 参考代码 T2 星港远航 题目大意 从位置 000 出发，要到达位置 LLL。初始有能量 PPP，每走 111 单位距离消耗 111 能量。沿途有若干补给站，第 iii 个补给站在位置 xix_ixi ，可以提供 aia_iai 的能量，每个站最多使用一次。求最少需要使用多少个补给站才能到达终点，若无法到达输出 −1-1−1。 题解思路 这是一个典型的贪心问题。关键在于：当当前能量不足以继续前进时，应该从之前经过的所有补给站中选择补给量最大的那个来使用。 先将所有补给站按位置排序，并把终点看成一个位置为 LLL、补给量为 000 的虚拟站。设当前最远能到达的位置为 reachreachreach，初始为 PPP，同时用一个大根堆维护所有已经经过的补给站的补给量。 从左到右扫描每个站： 如果当前站的位置 xi≤reachx_i \le reachxi ≤reach，说明可以到达，就把该站的补给量加入堆中；如果 xi>reachx_i > reachxi >reach，说明当前无法到达这个站，此时必须从堆中取出最大补给量来补充能量，使 reachreachreach 增大，并统计一次补给操作。重复这个过程，直到可以到达当前站或者堆为空。 如果堆为空仍无法前进，说明无法到达终点，输出 −1-1−1。否则最终成功走到终点，补给次数就是答案。 这个贪心策略的核心在于：每次必须补给时，选择补给量最大的站，可以让当前可达距离尽可能远，从而减少后续补给次数，是最优选择。 参考代码 T3 霓虹线路 题目大意 给定一棵有 nnn 个点的树，需要给每条边染色，颜色编号为 1∼k1\sim k1∼k。要求对于任意一个点，与它相连的所有边颜色必须两两不同。判断是否存在合法方案，若存在输出任意一种。 题解思路 树的边染色要求“每个点相邻边颜色两两不同”，这就是树上的proper edge coloring。设树的最大度数为 Δ\DeltaΔ。必要条件是 k≥Δk\ge \Deltak≥Δ：因为度为 Δ\DeltaΔ 的点周围 Δ\DeltaΔ 条边必须用不同颜色。 对树而言这也是充分条件：当 k≥Δk\ge\Deltak≥Δ 时一定能染色。构造方法用一次 DFS 从根向下分配颜色即可。 把树以 1 为根。对每个点 uuu，设与父边的颜色为 parColor[u]（根为 0）。我们给 uuu 的所有子边依次分配颜色 1..k，但跳过 parColor[u]，并且同一节点内部不重复。因为 uuu 的子边数是 deg(u)-1（根是 deg(u)），而 deg(u)≤kdeg(u)\le kdeg(u)≤k，所以总能分配完且不会用到第 k+1k+1k+1 种颜色。 实现上先用栈/队列求出父子关系，再按父到子的顺序给边赋色，复杂度 O(n)O(n)O(n)。 若 k<Δk<\Deltak<Δ，直接输出 NO。 参考代码 T4 雾港灯串 题目大意 给定一个长度为 nnn 的 01 串，可以通过翻转某一位（0↔10 \leftrightarrow 10↔1）来修改它。要求最终得到的新串满足：任意连续长度为 444 的子串中，111 的个数不能恰好为 333。求最少需要翻转多少次。 题解思路 本题的约束只涉及长度为 4 的相邻窗口，因此可以用“最近若干位作为状态”的线性 DP。设我们从左到右构造目标串 bbb，当决定了当前位置的值后，未来只会和“最近 3 位”共同组成新的长度为 4 的窗口，所以只需记住最后 3 位即可。 用一个 3 位二进制掩码 mask 表示当前已构造前缀的最后 3 盏灯（从左到右依次是更早到更晚）。令 dp[mask] 为构造到当前位置之前的最少翻转次数。处理第 iii 位时，尝试把 bib_ibi 取为 0 或 1： * 若 i≥4i\ge 4i≥4，则长度为 4 的窗口正好是“上一状态的 3 位 + 当前选择的 1 位”，对应一个 4 位数 w=(mask<<1)|b_i，若 popcount(w)==3 则该选择非法； * 否则（前 3 位）没有形成长度为 4 的窗口，不需要检查。 代价增加为 [s_i\ne b_i]，新状态为 ((mask<<1)&7)|b_i。每步转移常数只有 16 次，整体复杂度为 O(n)O(n)O(n)，空间为 O(1)O(1)O(1)。 最终答案是处理完全部位置后所有 dp[mask] 的最小值。 参考代码 T5 星灯选址 题目大意 给定一个长度为 nnn 的数组 aia_iai ，表示在第 iii 个位置放置星灯的收益（可以为负）。要求选择若干位置，使得不能选择相邻位置，并且总收益最大。同时需要输出一种最优方案。 题解思路 这是经典的线性 DP。设 dp[i] 表示只考虑前 i 个位置能得到的最大收益，则第 i 个位置要么不选，要么选： * 不选 i：收益 dp[i-1] * 选 i：则 i-1 不能选，收益 dp[i-2] + a_i 所以递推为 dp[i]=max⁡(dp[i−1],dp[i−2]+ai).dp[i]=\max(dp[i-1], dp[i-2]+a_i). dp[i]=max(dp[i−1],dp[i−2]+ai ). 边界 dp[0]=0，dp[1]=max(0,a_1)。为了输出方案，用一个数组记录每个 i 是通过哪种转移得到的，最后从 i=n 反向回溯即可。复杂度 O(n)。 参考代码 T6 分裂晶体 题目大意 给定一棵以 1 号节点为根的树，每个节点有一个整数能量值。要求通过任意重排每个节点的子树顺序，生成字典序最小的先序遍历序列。 题解思路 对任意节点 u，设它的“最稳定子序列” S(u) 是在允许重排 u 的孩子后，u 的子树先序序列中字典序最小的那条。显然整棵树的答案就是 S(1)。 如果 u 的孩子子树最稳定子序列分别是 S(v1),S(v2),…，那么 S(u) 一定形如： S(u) = [a_u] + S(按某顺序排列的孩子 1) + S(孩子 2) + … 为了让拼接后的整体字典序最小，只需把孩子按各自的 S(v) 的字典序从小到大排序后依次拼接即可：因为先序序列在进入第一个孩子子树前已经固定为 a_u，之后最先产生差异的位置一定落在“第一个不同孩子的子序列”里，所以把最小的子序列放在最前是最优的。 因此问题变成：需要能高效比较两个子树的 S(u) 与 S(v)。直接把 S(u) 展开成数组会导致总长度平方级。 做法是把每个 S(u) 当成一条“序列对象”，用一棵隐式 Treap 维护： * 长度 len； * 两个模数下的多项式哈希值； * 支持 O(log n) 取第 k 个元素、取前缀哈希。 比较两个序列时，用二分 + 前缀哈希求它们的最长公共前缀 LCP，再比较下一位元素即可完成字典序比较。对子树排序后，用 Treap 进行序列拼接（merge）即可得到父节点的序列对象。 整体流程：先把树以 1 为根，得到父子关系与后序顺序；按后序从叶到根处理，每个节点对孩子排序并合并生成自己的序列对象，同时把排序结果存下来。最后按存下来的孩子顺序做一次先序遍历输出能量值。 复杂度：设比较一次序列为 O(log^2 n)，则总复杂度约为 O((n + 总排序比较次数)·log^2 n)，在本题规模内可通过；空间 O(n)。 参考代码

问:罐头

如图，这是我的罐头 问你们的罐头?

真希望雨能下不停 雨爱的秘密 能一直延续

（模拟赛记录） 同步在洛谷更新 2026.03.23 A > TTT 组数据，每组数据给 nnn 个数 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an ，每个数的值要么是 000 要么是 111。现在对每个 i=1…ni=1\ldots ni=1…n 告诉你 bi=∑j=1i−1ajb_i=\sum\limits_{j=1}^{i-1}a_jbi =j=1∑i−1 aj 的值，问是否存在这样的 aaa 序列。 > > Data Range: 1≤T≤10,1≤n≤105,0≤bi≤1091\le T\le 10,1\le n\le 10^5,0\le b_i\le 10^91≤T≤10,1≤n≤105,0≤bi ≤109。 预计难度：*800 / 橙 题解： 显然只需要满足 b1=0b_1=0b1 =0 且 bi−bi−1∈{0,1}b_i-b_{i-1}\in\lbrace 0,1\rbracebi −bi−1 ∈{0,1} 即可。时间复杂度为 O(n)O(n)O(n)。 B P3594 [POI 2015 R3] 狼坑 Trous de loup 预计难度：*2000 / 蓝 容易发现删除的区间长度为 ddd 一定不会更差。直接枚举删除的区间 [l,l+d−1][l,l+d-1][l,l+d−1] 看上去就很没有前途，因此考虑换一个角度处理。注意到最长符合条件的区间长度满足单调性，因此考虑二分答案，然后再枚举删除的区间 [l,r][l,r][l,r]，选择一个被完全覆盖的长度为 ddd 的区间删除，这个地方肯定是贪心的选和最大的，因此求个前缀和之后二维数点ST 表就可以做到整体时间复杂度 O(nlog⁡n)O(n\log n)O(nlogn) 解决问题。 注意数组大小是 10610^6106 而不是 5e55e55e5。（赛时 nnn 的范围是 1e6 而不是 2e6） C 题意： > 给定一个 1∼n1\sim n1∼n 的排列 ppp，你需要计数有多少个 1∼n1\sim n1∼n 的排列 qqq，使得 qqq 是 ppp 的好排列。答案对 109+710^9+7109+7 取模。 > > 定义 aaa 是 bbb 的好排列，当且仅当 i=1…ni=1\ldots ni=1…n，若 ai≠na_i\neq nai =n 则执行操作 swap(bai,bai+1)swap(b_{a_i},b_{a_i+1})swap(bai ,bai +1 )。若操作全都执行之后 bbb 排列单调递增，则 aaa 是 bbb 的好排列。 > > Data Range: 1≤n≤50001\le n\le 50001≤n≤5000。 预计难度：*2500 / 紫 考虑套路的转化可行条件。容易发现题目给出的条件等价于：一个序列 qqq 是合法的当且仅当删除 qqq 序列的 nnn 后得到的序列 ttt 从后往前操作可以把升序排列变为 ppp。因此答案就是 nnn 乘以能够得到排列 ppp 的序列 ttt 的数量。 更确切的说：记 sis_isi 表示当前操作交换 ai,ai+1a_i,a_{i+1}ai ,ai+1 两个数，则对于长度为 n−1n-1n−1 的排列 ttt，操作过程可以看作是：从排列 1,2,3,…,n1,2,3,\ldots,n1,2,3,…,n 开始按顺序执行操作 st1,st2,…,stn−1s_{t_1},s_{t_2},\ldots,s_{t_n-1}st1 ,st2 ,…,stn −1 并最终得到 ppp 排列。最后答案额外乘以 nnn。 注意到若 ∣i−j∣>1|i-j|>1∣i−j∣>1，则 sis_isi 和 sjs_jsj 两个操作调换顺序不会影响最后得到的排列。考虑记 did_idi ：若 di=1d_i=1di =1 则表示 iii 在 ttt 中出现在 i+1i+1i+1 的前面，否则（di=0d_i=0di =0）表示 iii 在 ttt 中出现在 i+1i+1i+1 的后面。此时考虑把 1,2,3,…,n−11,2,3,\ldots,n-11,2,3,…,n−1 看作是图上的若干结点，则若 di=1d_i=1di =1 则连一条 i→i+1i\to i+1i→i+1 的边，否则连一条 i+1→ii+1\to ii+1→i 的边。则此时 ttt 正好是这张有向图的一个拓扑序。 记 S1,S2S_1,S_2S1 ,S2 两个集合为：S1={i+1∣di=1},S2={i+1∣di=0}S_1=\lbrace i+1\mid d_i=1\rbrace,S_2=\lbrace i+1\mid d_i=0\rbraceS1 ={i+1∣di =1},S2 ={i+1∣di =0}。则最终得到的置换 ppp 一定存在一个循环分解形如 1,S1,n,S21,S_1,n,S_21,S1 ,n,S2 的形式，且 S1S_1S1 一定是升序排列的，S2S_2S2 一定是降序排列的。 此时套路的记 π\piπ 为 ttt 的逆排列，则 ddd 的限制条件形如： * di=1d_i=1di =1：πi<πi+1\pi_i<\pi_{i+1}πi <πi+1 * di=0d_i=0di =0：πi>πi+1\pi_i>\pi_{i+1}πi >πi+1 问题变为计数有多少个长度为 n−1n-1n−1 的排列满足上述 ddd 对 π\piπ 的限制。因此考虑套路的 dp：设 fi,jf_{i,j}fi,j 表示当前处理了排列的前 iii 个元素，满足 ddd 的前 i−1i-1i−1 个限制，且最后一个数是这 iii 个数里第 jjj 小的元素。则转移枚举下一个数的排名可以做到 O(n3)O(n^3)O(n3)。注意到转移的是一段连续的区间因此使用前缀和维护，时间复杂度优化到 O(n2)O(n^2)O(n2) 可以通过该题。 D 题意： > 有一个 nnn 个结点的树，iii 点的点权是 aia_iai 。 > > QQQ 次询问，每次给定两个点 u,vu,vu,v，问 uuu 到 vvv 的唯一简单路径重排之后是否可以是回文的。若可以则输出 Meow 然后把 uuu 到 vvv 唯一简单路径上每个元素的值重排为字典序最小的 010101 回文串，否则输出 Wolf。 > > Data Range: 1≤n,Q≤1051\le n,Q\le 10^51≤n,Q≤105 预计难度：无法评定 / 紫 题解：用重剖查询 u∼vu\sim vu∼v 路径上 0,10,10,1 的数量，记 000 的数量为 c0c_0c0 ，111 的数量为 c1c_1c1 ，则若 c0,c1c_0,c_1c0 ,c1 都是奇数则无法构造回文串，否则特判 c0=0,c0=1,c1=0c_0=0,c_0=1,c_1=0c0 =0,c0 =1,c1 =0 的情况，然后分类讨论 c0 mod 2c_0\bmod 2c0 mod2 的值分类讨论即可。写起来代码是一坨。 attention：重剖没有必要用倍增来维护（（（ 2026.03.25 A 预计难度：*2100 / 蓝 Tag：概率期望，Exchange-Argument 题意 有 nnn 个二元组，每个二元组有参数 (pi,li)(p_i,l_i)(pi ,li )。你需要求出对于所有二元组的 n!n!n! 种排列顺序，其魅力值最大是多少。 定义 (p1,l1),(p2,l2),…,(pn,ln)(p_1,l_1),(p_2,l_2),\ldots,(p_n,l_n)(p1 ,l1 ),(p2 ,l2 ),…,(pn ,ln ) 的魅力值为： * 有一个总动力值 sss，初始为 000，还有一个魅力值 mmm，初始也为 000。 * 对于 i=1…ni=1\ldots ni=1…n，有 pip_ipi 的概率让总动力值 sss 和魅力值 mmm 同时增加 lil_ili ，有 1−pi1-p_i1−pi 的概率让魅力值 mmm 增加 s−lis-l_is−li 。 Data Range: 1≤n≤2×1051\le n\le 2\times 10^51≤n≤2×105。 题解 出题人样例只给 n=2n=2n=2，素质低下。 考虑直接 Exchange-Argument，对于两个二元组 (pi,li)(p_i,l_i)(pi ,li )，(pj,lj)(p_j,l_j)(pj ,lj )，计算其先执行 iii 后执行 jjj 和先执行 jjj 后执行 iii 两类情况对答案的影响，做差解不等式就可以得到排序条件。总时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)，没什么好说的。 挂分原因 挂成 40 了，原因是拆括号拆错了（但是因为赛时还拼了一个爬山所以小数据拍不出来问题 :( B 预计难度：*3000 / 黑（难度全在代码实现和细节处理上，鉴定为大份） Tag：数据结构，点分治，分类讨论 题意 有一个 nnn 个点的树，你还有 mmm 个二元组，第 iii 个二元组是 (xi,yi)(x_i,y_i)(xi ,yi )。现在你需要找出 1≤i≤j≤m1\le i\le j\le m1≤i≤j≤m 使得 D(xi,xj)+D(yi,yj)D(x_i,x_j)+D(y_i,y_j)D(xi ,xj )+D(yi ,yj ) 的值最大，其中 D(i,j)D(i,j)D(i,j) 表示在树上 iii 点到 jjj 点的唯一简单路径上边的数量。 Data Range: 1≤n,m≤5×1051\le n,m\le 5\times 10^51≤n,m≤5×105。 题解 后面为了方便，记 d(i,j)=D(xi,xj)+D(yi,yj)d(i,j)=D(x_i,x_j)+D(y_i,y_j)d(i,j)=D(xi ,xj )+D(yi ,yj )。 考虑分别对 x,yx,yx,y 两个维度做点分治。先考虑 xxx 维度：设当前点分治处理的重心是 ccc，则若 xi,xjx_i,x_jxi ,xj 删除 ccc 后属于不同的树或 xi,xjx_i,x_jxi ,xj 中有一个值为 ccc，那么 xi→xjx_i\to x_jxi →xj 的唯一简单路径一定经过点 ccc。因此有 D(xi,xj)=D(xi,c)+D(xj,c)D(x_i,x_j)=D(x_i,c)+D(x_j,c)D(xi ,xj )=D(xi ,c)+D(xj ,c)，即 d(i,j)=D(xi,c)+D(yj,c)+D(yi,yj)d(i,j)=D(x_i,c)+D(y_j,c)+D(y_i,y_j)d(i,j)=D(xi ,c)+D(yj ,c)+D(yi ,yj )。此时考虑记 wj=D(xj,c)w_j=D(x_j,c)wj =D(xj ,c) 那么对当前的 iii 二元组只需要求出 max⁡j(wj+D(yi,yj))\max\limits_j(w_j+D(y_i,y_j))jmax (wj +D(yi ,yj )) 的最大值加上 D(xi,c)D(x_i,c)D(xi ,c) 即可。 此时问题被转化为：有 mmm 个点 yiy_iyi 带权 wiw_iwi ，支持插入一个点 (yi,wi)(y_i,w_i)(yi ,wi ) 和查询一个点 yiy_iyi 的 max⁡j(wj+D(yi,yj))\max\limits_j(w_j+D(y_i,y_j))jmax (wj +D(yi ,yj )) 两个操作。此时考虑再对 yyy 维度做一次点分治，此时把 yyy 按照其在 xxx 维度上删掉点 ccc 后属于的子树分类处理，然后大力分类讨论即可。总时间复杂度为 O(nlog⁡2n)O(n\log^2n)O(nlog2n)，细节有一车，写起来非常赤石。 扩展 可以把二元组扩展成 kkk 元组，这样可以做 kkk 轮点分治，时间复杂度为 O(nlog⁡kn)O(n\log^kn)O(nlogkn)。当然没人想写这个。 挂分原因 挂成 80 分了，原因暂时未知，应该是哪个地方边界或者细节出了点小问题 C 预计难度：*1800 / 绿 Tag：容斥原理，分类讨论 题意 QQQ 次询问，每次询问给定四个区间 [l1,r1],[l2,r2],[l3,r3],[l4,r4][l_1,r_1],[l_2,r_2],[l_3,r_3],[l_4,r_4][l1 ,r1 ],[l2 ,r2 ],[l3 ,r3 ],[l4 ,r4 ]，问有多少个整数四元组 (a,b,c,d)(a,b,c,d)(a,b,c,d) 同时满足： * a∈[l1,r1]a\in[l_1,r_1]a∈[l1 ,r1 ] * b∈[l2,r2]b\in[l_2,r_2]b∈[l2 ,r2 ] * c∈[l3,r3]c\in[l_3,r_3]c∈[l3 ,r3 ] * d∈[l4,r4]d\in[l_4,r_4]d∈[l4 ,r4 ] * a≠b,b≠c,c≠d,d≠aa\neq b,b\neq c,c\neq d,d\neq aa=b,b=c,c=d,d=a Data Range: 1≤Q≤106,1≤li,ri≤109(i=1…4)1\le Q\le 10^6,1\le l_i,r_i\le 10^9(i=1\ldots 4)1≤Q≤106,1≤li ,ri ≤109(i=1…4)。 题解 根本不是题。。。。。。。 容易想到容斥计算答案，简单计算一下就可以发现答案可以被表示为：不考虑任何条件的方案数 - 钦定 a=ba=ba=b 的方案数 - 钦定 b=cb=cb=c 的方案数 - 钦定 c=dc=dc=d 的方案数 - 钦定 d=ad=ad=a 的方案数 + 钦定 a=b=ca=b=ca=b=c 的方案数 + 钦定 a=b=da=b=da=b=d 的方案数 + 钦定 a=c=da=c=da=c=d 的方案数 + 钦定 b=c=db=c=db=c=d 的方案数 + 钦定 a=b,c=da=b,c=da=b,c=d 的方案数 + 钦定 a=d,b=ca=d,b=ca=d,b=c 的方案数 - 三倍钦定 a=b=c=da=b=c=da=b=c=d 的方案数。 直接把上面所有情况都分类讨论出来即可，写的时候为了方便可以封装一个求线段交集的函数。 挂分原因 没挂 D 预计难度：*2700 / 紫 Tag：差分，并查集，扫描线，分类讨论 题意 给定一个长度为 nnn 的序列 sss，求 ∑1≤a≤b<c≤d≤nmax⁡(max⁡i=absi,max⁡i=cdsi)\sum\limits_{1\le a\le b<c\le d\le n}\max(\max\limits_{i=a}^bs_i,\max\limits_{i=c}^ds_i) 1≤a≤b<c≤d≤n∑ max(i=amaxb si ,i=cmaxd si ) 对 998244353998244353998244353 取模后的结果。 题解 这套题里最好的一道题（？ 直接对着这个式子做看着就很没有前途，因此考虑先做一个经典转化，记 f(v)f(v)f(v) 为所有同时满足 1≤a≤b<c≤d≤n,max⁡i=absi≤v,max⁡i=cdsi≤v1\le a\le b<c\le d\le n,\max\limits_{i=a}^bs_i\le v,\max\limits_{i=c}^ds_i\le v1≤a≤b<c≤d≤n,i=amaxb si ≤v,i=cmaxd si ≤v 的不同四元组 (a,b,c,d)(a,b,c,d)(a,b,c,d) 的数量，则答案显然可以表示为 ∑ii(f(i)−f(las))\sum\limits_ii(f(i)-f(las))i∑ i(f(i)−f(las))，其中 laslaslas 是比 iii 小的最大的不同值。 然后题目一下子就变得简单了。从小到大扫描所有值 iii，则 [a,b],[c,d][a,b],[c,d][a,b],[c,d] 两个区间必须都落在 si≤vs_i\le vsi ≤v 的部分中。用并查集维护所有这样的连续区间，记这些区间长度分别为 L1,L2,…,LkL_1,L_2,\ldots,L_kL1 ,L2 ,…,Lk （这个可以用并查集+扫描线简单维护），则此时分类讨论 [a,b][a,b][a,b] 和 [c,d][c,d][c,d] 在同一个连续区间内 / 不在同一个连续区间内两类情况讨论。 记 g1(x)g_1(x)g1 (x) 表示长度为 xxx 的连续段中放了一个区间的方案数，g2(x)g_2(x)g2 (x) 表示长度为 xxx 的连续段内放了两个区间的方案数，则显然有： g1(x)=x(x−1)2g2(x)=x(x−1)(x+1)(x+2)24g_1(x)=\frac{x(x-1)}2\\ g_2(x)=\frac{x(x-1)(x+1)(x+2)}{24} g1 (x)=2x(x−1) g2 (x)=24x(x−1)(x+1)(x+2) 答案也是好统计的，显然有：f(v)=∑i=1kg2(Li)+∑i=1k∑j=i+1kg2(i)g2(j)f(v)=\sum\limits_{i=1}^kg_2(L_i)+\sum\limits_{i=1}^k\sum\limits_{j=i+1}^kg_2(i)g_2(j)f(v)=i=1∑k g2 (Li )+i=1∑k j=i+1∑k g2 (i)g2 (j)。此时再记 s1=∑g1(Li),s2=∑g1(Li)2,sg=∑g2(Li)s_1=\sum g_1(L_i),s_2=\sum g_1(L_i)^2,s_g=\sum g_2(L_i)s1 =∑g1 (Li ),s2 =∑g1 (Li )2,sg =∑g2 (Li )，则可以用 s1,s2,sgs_1,s_2,s_gs1 ,s2 ,sg 来表示 f(v)f(v)f(v) 的值：f(v)=sg+12(s12−s2)f(v)=s_g+\frac12(s_1^2-s_2)f(v)=sg +21 (s12 −s2 )，在并查集维护区间连续段的时候顺带统计 s1,s2,sgs_1,s_2,s_gs1 ,s2 ,sg 的值即可。 挂分原因 挂成 90 分了，原因未知

浅谈线段树进阶用法(未完工)

前言 本文篇幅较长，里面包含了对线段树进阶用法的介绍和本人对此的理解，希望这篇文章能帮助你更好的掌握这些知识。(ps: 请你保证至少会基础线段树以及简单用法) Update: 于 2025年8月1日完成动态开点还有部分可持久化线段树。 Update: 于 2025年8月20日完成可持久化线段树进阶内容。 线段树动态开点 一般而言，线段树是一颗完全二叉树。但是有些题目需要我们维护较大的值域信息，这时候一般的建树方法并不适用，所以我们需要使用动态开点的方法。 回顾线段树基本原理，在值域极大的情况下，线段树在查询或修改时有些节点我们可能从始至终都不会用到，此时就没有必要把这样的节点保存。换句话说，我们按需分配，只保存需要访问的节点，这样就可以做到合适的复杂度了。注意，此时就不能直接建树了，更不能使用堆式存储法（因为我们的节点是动态储存的）。 实现有两种主流方法：第一，用取地址符更新节点。第二，直接函数返回编号。个人更倾向于好写简洁的第一种方法。 上面列举的是单点修改的做法，我们可以把这个过程理解为向线段树添加若干条链，查询时就在这颗稀疏二叉树上正常访问即可。 对于区间修改而言，下传懒标记时我们需要判断左右儿子是否存在，如果不存在需要新建。(注意这里的空间开销不小) 当值域远大于操作规模时我们的空间复杂度大概是 O(nlog⁡V)O(n \log V)O(nlogV) 的，时间复杂度同理，但是需要注意的一点是区间修改下传标记所需要的额外开销，一般需要开 303030 到 505050 倍不等，建议在不超过空间限制的情况下尽量将数组开大一些以保证正确性。 这里附送一道例题，需要支持区间修改和区间查询：CF915E Physical Education Lessons 可持久化线段树 前置知识：动态开点线段树. 该部分篇幅较长，请读者根据需求自行选择阅读。 持久化数据结构基础介绍 > " 可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本，并且支持操作的不可变特性 (immutable)。 ----- 摘自 OIwiki 在很多题目中，我们可以通过离线思想配合扫描线等算法批量处理问题，以达到优化复杂度的目的。但有些题目需要我们处理在线操作，这时就需要可持久化数据结构了。 所谓可持久化数据结构，就是支持对维护信息的历史版本做查询和修改的数据结构。我们对可持久化数据结构的操作自由度将其分为四类： * 部分可持久化：可以访问所有版本，但是只支持修改最新版本。 * 完全可持久化：所有版本都可以访问修改。 * 可合并可持久化：在完全可持久化的基础上，支持将两个历史版本合并。 * 函数式可持久化：函数式编程中实现的持久化数据结构，对象都是只读的，任意修改都是创建一个新的节点，而不是在旧节点上修改。 以上四种持久化是逐步增强的，后者包含于前者。在算法竞赛中，我们一般只在意前两种可持久化结构。 简介和说明 可持久化线段树，又被称之为主席树，由 NOI 选手黄嘉泰（HJT）发明。（有个有趣的说法，称其发明原因是发明者当时不会写划分树，从而用此结构替代) 而很多地方也称主席树为可持久化权值线段树，这些叫法五花八门，初学者需要理清这些概念，避免混淆，这里均使用全名可持久化线段树。 原理实现 首先我们先介绍一下权值线段树，就是对于一个固定的序列维护一颗线段树，每个数按其权值为下标插入线段树中并维护值域信息。容易发现，我们可以通过线段树二分的方式做到 O(log⁡n)O(\log n)O(logn) 的时间求全局第 kkk 大。 由此，我们引出一道经典题目：给定由 nnn 个正整数构成的序列 aaa，对于指定的闭区间 [l,r][l, r][l,r] 查询其区间内的第 kkk 小值。 首先，我们假设对区间 [l,r][l,r][l,r] 内的树构造一颗值域线段树，那么问题就转化为了全局第 kkk 大。我们发现，实际上每个数的出现次数可以差分处理。比如说我们需要计算 [l,r][l,r][l,r] 内数 xxx 的出现次数，就可以通过 [1,r][1,r][1,r] 中 xxx 的出现次数减去 [1,l−1][1,l-1][1,l−1] 中 xxx 出现的次数得到答案。 也就是说，我们可以参考前缀和的思想维护 nnn 棵值域线段树，第 iii 棵线段树维护区间 [1,i][1,i][1,i] 内的桶信息，查询时就可以通过对第 rrr 棵线段树和 l−1l-1l−1 棵线段树作差得到区间上线段树的实际信息。 至于如何维护这 nnn 棵线段树，其实也不是一件麻烦事。沿用上文线段树动态开点的思想，容易发现第 iii 棵线段树的维护信息与第 i−1i-1i−1 棵线段树仅有一个数 aia_iai 之差，换到线段树上只是多了一条长度为 log⁡n\log nlogn 的链而已。故用一个数组 rtrtrt 记录每个线段树的根，记录左右儿子的基础上动态开点就可以了。 这里引用了 OIwiki 里的例子，下图表现了修改 [1,8][1,8][1,8] 中 111 的例子： 注意，我们实际上每次插入是直接新建节点的，与之前这个节点是否出现过无关。实际上，可持久化线段树形成的结构严格来说并不是一棵树，因为一个节点可能被多个父节点引用，但这并不影响我们查询信息。 插入的具体实现也是较为简单的，类似动态开点的技巧我们每次新建一个节点，再把前驱节点的信息复制给它，并对信息做相应的更新。 在值域不大的时候我们可以先建一颗空树，然后再像上图一样依次插入，就避免了空节点无法复用的麻烦。如果避免不了值域大的问题，我们就只能参考动态开点的方式每次新建节点。 事实上，由于线段树的树高在 log⁡n\log nlogn 量级，所以每插入一个数我们所需要的空间是 O(log⁡n)O(\log n)O(logn) 左右，这意味着一颗可持久化线段树所需空间是 O(nlog⁡n)O(n \log n)O(nlogn) 量级的。 下面给出【模板】可持久化线段树 2 基于可持久化线段树的实现： 实际上很多可持久化线段树问题的空间限制非常宽松，我们完全可以和实现动态开点线段树时一样在不超空间的限制下尽可能多开线段树节点。 进阶用法 可持久化线段树实际上也有很多扩展用法，比如差分统计信息或处理偏序问题，建议读者在掌握其基础用法后再阅读本部分。 配合树上差分 在序列上查询信息我们可以通过差分达到目的，在树上我们可以通过树上差分的方式解决问题。 比如说这道题：P2633 Count on a tree，要求我们在线回答树上路径第 kkk 小。 考虑树上差分的方式，我们用第 iii 颗线段树表示根节点 111 到 iii 路径上所有点的信息。类似序列上的做法在深度优先搜索的时候顺便维护即可，查询时用树上差分的技巧维护链信息即可。 区间修改 这部分可能会有些难以理解，请读者先掌握基本用法。 很多人初学主席树可能会有一个误区：它不支持区间修改还有区间查询。这个想法我可以很明确的告诉你：它大错特错。现在我们来通过解决一道数据结构题来展开讲解。 首先我们先不考虑可持久化的问题，发现实际上加操作是很好维护的，但推平操作很难维护。所以在这里我们有一个重要观察: m≤4m \le 4m≤4，这意味着可以支持对行状态压缩。 我们设 fS,j=∑i∈SAi,jf_{S,j} = \sum_{i \in S} A_{i,j}fS,j =∑i∈S Ai,j 。令满状态 p=2m−1p = 2^m-1p=2m−1，那么我们只需要在意 fp,jf_{p,j}fp,j 。只有一行的区间推平操作是好维护的，我们只需要在下传标记的同时更新所有与操作行相关的状态 SSS 即可。比如说我要把第 iii 行某个区间修改成 xxx(这里从 000 开始标号)，对于区间内所有满足 i∈Si \in Si∈S 的状态，我们直接让 fS,j=fS−i,j+xf_{S,j} = f_{S-i,j} + xfS,j =fS−i,j +x。注意这里我们需要从小到大依次更新，并且只需要更新对应的状态。 将上述更新方法沿用至线段树上，我们就做到了用 2m−12^m-12m−1 颗线段树维护推平操作了，至于加操作是同理的，我们只需要处理所有有关的状态对应的线段树。这里建议开一颗线段树，然后维护 2m−12^m-12m−1 个状态，或许会好写一点。 这里提供下传标记的代码： 我们回到可持久化的问题，类比单点修改，区间修改实际上也是在一个版本基础上进行节点信息复制。对需要访问的节点新建版本，否则直接继承版本基础的节点。 然后考虑下传标记的问题，由于我们并不知道每个节点的对应的版本，所以每次我们都需要新建节点，读者可以观察上述代码中 down 函数的第一行。 也就是说，我们在每次区间修改时对访问节点新建，下传标记时新建节点。这样就做到了维护区间修改还有区间查询的问题了，打破了其仅能通过差分进行区间查询的局限性。 这里提供此题的参考代码（std）。若对解决此题感兴趣，可私信作者获取题目或测试数据。 很多题目没有让可持久化线段树支持区间修改与查询的原因在于巨大的空间开销，同时这里依然建议多开节点保证正确性。 线段树合并 前置知识：权值线段树，动态开点线段树。 该内容比较简单，读者可以只是稍作了解。 简介和说明如果没有特殊说明，这里默认 nnn 和值域 VVV 同阶。 一般而言，权值线段树的操作空间实际上是很小的，因为它只支持修改某些数的出现次数，遇到一些复杂度操作就不行了，比如可重集合并类似的操作。这时候我们就需要引入线段树合并这一概念了。 原理实现 事实上合并两个集合我们有一个非常公式化的做法：启发式合并。只需要每次把较小的集合元素全部加入到另一个集合当中，这样发现对于每个较小集合元素，所在新集合大小至少为原来的两倍，所以一个元素至多被加入 O(log⁡n)O(\log n)O(logn).权值线段树套用启发式合并的方法可以做到 O(nlog⁡2n)O(n \log^2 n)O(nlog2n)。 但事实上这个复杂度并不优秀，如果我们能够快速的维护两个节点内合并的信息那就可以使用线段树合并的技巧做到 O(nlog⁡n)O(n\log n)O(nlogn)。 线段树合并的过程实际上非常简单，大概率你能直接推导出如何合并。 假设有两个需要合并的线段树 A 和 线段树 B（其中我们把线段树 B 的信息插入至线段树 A），我们考虑同时递归搜索这两棵树并讨论访问到某个节点的情况。 如果 A 树对应节点为空，那么我们直接复用 B 树节点。 如果 B 树对应节点为空，直接返回 A 树对应节点。 综上所述：如果 A 树或 B 树的对应节点为空，那么就直接返回另一颗树上的节点，否则递归到叶子节点时，我们合并两棵树对应节点并返回，并在整个过程中更新维护的信息。 从刚刚的算法流程中不难看出，一次线段树合并的复杂度是 O(两颗线段树公共部分) O(两颗线段树公共部分)O(两颗线段树公共部分) 的。由于数的总量为 O(nlog⁡n)O(n \log n)O(nlogn) 合并量级总会不超过 O(nlog⁡n)O(n \log n)O(nlogn)。但是空间常数也是巨大的，此时可以写个可并堆（左偏树）。 下面给出模版题 P4556 基于线段树合并的做法。（本题只需要使用树上差分的技巧，最后树上每个节点合并儿子对应线段树即可）