[JOI Final 2026] 集邮 5 / Collecting Stamps 5
淀粉质好题！
[JOI Final 2026] 集邮 5 / Collecting Stamps 5。
给定 nnn 个点的树，第 iii 个点点权为 aia_iai。
给定常数 DDD，试对于每一个 iii，求出满足以下条件的 jjj 的个数：
提取出 i,ji,ji,j 路径上的所有点，依次排开为 p0,p1,⋯ ,pmp_0,p_1,\cdots,p_mp0,p1,⋯,pm，其中 p0=i,pm=jp_0=i,p_m=jp0=i,pm=j；
存在一个 0≤x≤m0\le x\le m0≤x≤m，使得 dist(i,px)≥apx\text{dist}(i,p_x)\ge a_{p_x}dist(i,px)≥apx。
n≤4×105n\le 4\times 10^5n≤4×105，0≤D≤n0\le D\le n0≤D≤n，0≤ai≤n0\le a_i\le n0≤ai≤n。
子任务 1：n≤3000n\le 3000n≤3000；
子任务 2：D=n−1D=n-1D ...
[JOI Open 2025] 冒泡排序机 / Bubble Sort Machine
[JOI Open 2025] 冒泡排序机 / Bubble Sort Machine。
经验：[ICPC 2023 Seoul R] Apricot Seeds。
给定长度 nnn 的数组 aaa，求冒泡排序第 KKK 轮后区间 [l,r][l,r][l,r] 的和。
n≤5×105n\le 5\times 10^5n≤5×105。
首先看到区间 [l,r][l,r][l,r]，先转化为前缀和 [1,x][1,x][1,x]。
然后考虑刻画冒泡排序的结果。
先看看冒泡排序第一轮的结果 a′a'a′。那么对于第 111 个位置，显然排序后其值为 min{a1,a2}\min\{a_1,a_2\}min{a1,a2}。
然后是第二个位置。因为 a1′=min{a1,a2}a'_1=\min\{a_1,a_2\}a1′=min{a1,a2}，所以交换第一个数后 a2′=max{a1,a2}a'_2=\max\{a_1,a_2\}a2′=max{a1,a2}；然后又因为第二个数 ...
[JOIG 2024] 感染シミュレーション / Infection Simulation
有 nnn 个顾客，第 iii 的顾客存在时间为 [li,ri][l_i,r_i][li,ri]。
如果一个顾客 iii 存在的时间中，与被感染的顾客一起存在了 ≥x\ge x≥x 的时间，那么顾客 iii 也会被感染。
多次询问，每次给定 p,xp,xp,x，求如果 ppp 顾客被感染了，且给定感染系数为 xxx，有多少个顾客会被感染。
n≤105n\le 10^5n≤105。
子任务：p=1p=1p=1，且 l,rl,rl,r 随 iii 单调不减。
要想充要的转化。
先看子任务。
此时顾客 111 会最先被感染。然后根据 l,rl,rl,r 单调不降，感染顺序一定是 1,2,⋯1,2,\cdots1,2,⋯。那么只需要满足相邻两个能传染即可，可以使用 ST 表 O(logn)\mathcal{O}(\log n)O(logn) 的查询。
接着看正解。
首先我们肯定要将 lll 为第一关键字，rrr 会第二关键字排序。接下来讨论的下标均为排序后的下标。
引理 1：
存在顾客被感 ...
[JOI Final 2026] 花园 3 / Garden 3
有一个长 HHH 宽 WWW 的矩形花园。
有 nnn 次操作。
第 iii 次操作会将矩形范围 Ui≤x≤Di,Li≤y≤RiU_i\le x\le D_i,L_i\le y\le R_iUi≤x≤Di,Li≤y≤Ri 的 (x,y)(x,y)(x,y) 的点权 +Ci+C_i+Ci，初始时所有点权均为 000。
给定常数 XXX，每次修改后，求面积最小的矩形的面积使得其可以覆盖所有点权 ≥X\ge X≥X 的点。
H,W≤109,n≤2×105H,W\le 10^9,n\le 2\times10^5H,W≤109,n≤2×105；
Ci≤109,X≤2×1014C_i\le 10^9,X\le 2\times 10^{14}Ci≤109,X≤2×1014。
这题需要仔细分析就能轻松写出。
首先将求面积转化为求出 ≥X\ge X≥X 的点中 xxx 坐标和 yyy 坐标最小/最大的坐标是多少。
显然这四个本质相同，因此只考虑求出 xxx 坐标最小的。
然后由于答案必然越来越小，因此可以考虑扫描线，枚举 ...
[JOI 2026 SemiFinal] 新的桥梁 / New Bridge
给一个 nnn 个点 mmm 条边的带权图。
定义 Ds,iD_{s,i}Ds,i 表示以 sss 作为起点执行 Prim 最小生成树算法，iii 是第几个被扩展到的。
多次询问，每次给定 xxx，求 ∑sDs,x\sum\limits_s D_{s,x}s∑Ds,x。
n≤3×105,m≤6×105n\le 3\times10^5,m\le 6\times 10^5n≤3×105,m≤6×105。
所有边边权互不相同。
首先给出一个样例：
1234564 51 3 12 3 23 4 34 2 41 4 5
可以先模拟以下，以加深对题解的理解。
由于 Prim 算法求出的最小生成树和 Kruskal 一致，不妨考虑 Kruskal 以及 Kruskal 重构树。
对于 Kruskal 重构树上的一个非叶子节点，其代表一条边，连接两个连通块 S1,S2S_1,S_2S1,S2，那么所有会先到 S1S_1S1 的节点必然会至少为 S2S_2S2 中的每一个节点添加 ∣S1∣|S_1|∣S1 ...
矩形（rectangle）
给定 n×nn\times nn×n 的 010101 矩形。mmm 次询问，每次询问求有多少个 aaa 行 bbb 列的矩形满足其边上均为 111。
n,m≤1500n,m\le 1500n,m≤1500，时限 5s5s5s。
首先套路性的求出 ri,jr_{i,j}ri,j 表示 (i,j)(i,j)(i,j) 右边最长可以延伸的长度，di,jd_{i,j}di,j 表示 (i,j)(i,j)(i,j) 下面最长可以延伸的长度。
然后一个矩形 (i,j)(i+a−1,j+b−1)(i,j)(i+a-1,j+b-1)(i,j)(i+a−1,j+b−1) 合法当且仅当：
[ri,j≥b][di,j≥a][di,j+b−1≥a][ri+a−1,j≥b][r_{i,j}\ge b][d_{i,j}\ge a][d_{i,j+b-1}\ge a][r_{i+a-1,j}\ge b]
[ri,j≥b][di,j≥a][di,j+b−1≥a][ri+a−1,j≥b]
这是一个偏序问题，可以使用 bitset 解决。
不妨设 bitset Ri,j,k ...
覆盖（cover）
你有 nnn 个点的树，初始每一条边都没有颜色。
你有两种覆盖操作：
选择 u,vu,vu,v 满足 u,vu,vu,v 路径上的边都没有颜色，然后将他们路径 u,vu,vu,v 上的边都染色。
选择 uuu 满足 uuu 的邻边都没有被染色，然后将 uuu 的邻边染色。
要求用最少次数将所有边染色。
n≤105n\le 10^5n≤105。
首先你应该模拟大样例。
然后观察以 xxx 为根的最优解结构：必然为如下两种状态：
在这个点执行了邻边覆盖，那么这个点就会覆盖其父边。然后其就需要累加每一个儿子的答案，因为一个邻边覆盖会切断 xxx 与儿子的联系。但是儿子的父边不能被覆盖。所以，我们至少应该设出关于 xxx 的两个状态：fx,0/1f_{x,0/1}fx,0/1 表示 xxx 有/没有覆盖父边。那么只需要 fx,0←fu,1f_{x,0}\leftarrow f_{u,1}fx,0←fu,1。
这个点不执行任何东西。那么他需要将儿子和连接儿子的边进行连接，然后转移。然后你就会发现这样一个结构：如果说 xxx 有 CCC 个儿子没有覆盖其父边， ...
二进制翻转（rev）4
给定 n≤1015n\le 10^{15}n≤1015，定义 r(i)r(i)r(i) 表示 iii 二进制翻转后的结果，c(i)c(i)c(i) 表示 iii 二进制下 111 的个数，求：
∑i=0nc(i+r(i))\sum_{i=0}^n c(i+r(i))
i=0∑nc(i+r(i))
本题解建立在上一篇题解和上上篇以及上上上篇的基础上进行了一些优化。
首先先写出我们的状态定义：
定义 fi,j,k,pf_{i,j,k,p}fi,j,k,p 表示：
考虑了高位 iii 和低位 iii 及以前的数位；
低位 iii 受到的进位 j=0/1j=0/1j=0/1；
高位 iii 以前最后一个 000 的位置 kkk；
高低位与限制的关系 p=0/1/2p=0/1/2p=0/1/2。
写成代码长这样：
int f[N][2][N][3]
看起来维度很高，但是实际上这里面很多都可以优化掉（目前我优化掉了一个 logn\log nlogn 的空间）。
观察所有的状态，容易发现这样一件事情：i,j,pi,j,pi,j,p 都难以优化，只有这个 kk ...
二进制翻转（rev）3
给定 n≤1015n\le 10^{15}n≤1015，定义 r(i)r(i)r(i) 表示 iii 二进制翻转后的结果，c(i)c(i)c(i) 表示 iii 二进制下 111 的个数，求：
∑i=0nc(i+r(i))\sum_{i=0}^n c(i+r(i))
i=0∑nc(i+r(i))
本题解建立在上一篇题解和上上篇的基础上进行了一些优化。
首先先写出我们的状态定义：
定义 fi,j,k,v,pf_{i,j,k,v,p}fi,j,k,v,p 表示：
考虑了高位 iii 和低位 iii 及以前的数位；
低位 iii 受到的进位 j=0/1j=0/1j=0/1；
高位 iii 以前最后一个 000 的位置 kkk；
状态 kkk 不存在或存在但没有进位，以及存在有进位，v=0/1v=0/1v=0/1；
高低位与限制的关系 p=0/1/2p=0/1/2p=0/1/2。
写成代码长这样：
int f[N][2][N][2][3]
看起来维度很高，但是实际上这里面很多都可以优化掉（目前我优化掉了 12\frac{1}{2}21）的空间）。
观察 ...
二进制翻转（rev）2
给定 n≤1015n\le 10^{15}n≤1015，定义 r(i)r(i)r(i) 表示 iii 二进制翻转后的结果，c(i)c(i)c(i) 表示 iii 二进制下 111 的个数，求：
∑i=0nc(i+r(i))\sum_{i=0}^n c(i+r(i))
i=0∑nc(i+r(i))
本题解建立在上一篇题解的基础上进行了一些优化。
首先写出上一篇题解的状态设计：
定义 fi,j,k,v,p,qf_{i,j,k,v,p,q}fi,j,k,v,p,q 表示：
考虑了高位 iii 和低位 iii 及以前的数位；
低位 iii 受到的进位 j=0/1j=0/1j=0/1；
高位 iii 以前最后一个 000 的位置 kkk；
状态 kkk 不存在，存在但没有进位，以及存在有进位，v=0/1/2v=0/1/2v=0/1/2；
高位有没有数位限制 p=0/1p=0/1p=0/1；
低位和数位限制的关系 q=0/1/2q=0/1/2q=0/1/2；
写成代码长这样：
int f[N][2][N][3][2][3];
看起来维度很高，但是实际上这里面 ...
