MiQiu

[L4] 树上差分 1. 生态位 识别: 批量路径修改: 给定 MMM 条路径 (u,v)(u, v)(u,v)，对路径上的所有点（或边）增加权值 www。 最终单次查询: 修改完成后，查询每个点（或边）的最终权值。 离线处理: 不需要在线回答每次修改后的状态，而是先修改完再统计。 地位: 树论与降维技巧的结合。它是处理静态树上路径覆盖问题的 O(N+M)O(N+M)O(N

CF2194E - The Turtle Strikes Back 1. 题面梗概 中译中： 小 A 从 (1,1)(1,1)(1,1) 走到 (n,m)(n,m)(n,m)，每经过一个格子 (i,j)(i,j)(i,j) 都会获得 ai,ja_{i,j}ai,j​ 的权值。但在小 A 出发后，捣蛋鬼小 BBB 会反转一个格子，ai,j→−ai,ja_{i,j} \to -a_{i,j}ai,j​

C - AtCoder Riko 1. 题意梗概 给定一个包含 NNN 个正整数的序列 AAA。这些数字是由若干根长度为 LLL 的零食经过摇晃后产生的。每根原始长度为 LLL 的零食要么保持完整，要么断成两截（长度和为 LLL）。 求所有可能的原始长度 LLL。 2. 逻辑推导 这其实是一个构造问题，注意到每个零食只有两种情况，所以我们可以把目光转移到最大值上。 情况一：AmaxA_{max

D - Many Repunit Sum 1. 题意梗概 给定 NNN 个整数 AiA_iAi​，对于每个 AiA_iAi​，定义 BiB_iBi​ 为由 AiA_iAi​ 个 1 组成的整数（例如 Ai=3→Bi=111A_i=3 \to B_i=111Ai​=3→Bi​=111）。求 ∑i=1NBi\sum_{i=1}^{N} B_i∑i=1N​Bi​ 的值。 2. 逻辑推导 最直接的想法就是

E - Sparse Range 1. 题意梗概 给定一个长度为 NNN 的数组 AAA 和一个正整数 DDD。 求有多少子区间 (L,R)(L, R)(L,R) 满足：区间内任意两个元素之差的绝对值都 ≥D\ge D≥D。 2. 逻辑推导 其实看到这个 子区间，计数，范围约束。很容易会想到滑动窗口（双指针）的写法。 起手就可以固定右端点 RRR，尝试寻找最小的合法左端点 LLL。 如果区间 [L