连续两场Rating–了，这个Rating到底咋算的啊，排行榜第一面都有人Rating绿了。。。

第〇纪元的新手Rating福利全当护盾用了是吧。。。

T1 二进制与一 IV

虽然看不懂标题为什么是这个。

但也不妨碍做题ovo

本题思路小总结：

• 将 $x$ 的二进制位从低到高存入数组，记录长度 $L$。
• 为使 $x⊕y$ 的二进制表示（不含前导零）为回文，需让对称位相等。
• 若某对对称位 $(i, L+1-i)$ 不同，则必须翻转其中一位；选择翻转低位（ $y$ 的对应位为 $1$ ）可使 $y$ 更小。
• 按从高位到低位的顺序构造 $y$ 的二进制位（先处理较大的 $i$ ），保证数值最小。
• 若对称位相同，则 $y$ 该位设为 $0$，不翻转。
• 遍历所有对称对后，得到的 $y$ 即为最小非负整数解。
• 时间复杂度 $O(T \log x)$，空间 $O(\log x)$，$x=0$ 时输出 $0$ 符合要求。

100pts

T2 小 L 涂色

很奇怪啊，为什么这题我花了一个小时才发现能把图拆成树和非树去想

刚开始还写了个暴力 结果zroi的大家几乎都在1h左右把这题A了 只有本蒟蒻在没有预提交的情况下3h才A QwQ

本题思路小总结：

• 每条边选一个端点涂色，未涂色点扣权值，求最小扣除和。
• 等价于给边定向，使入度为 $0$ 的点（未涂色）权值和最小。
• 连通分量若为树（$边数 = 点数 – 1$），则至少有一个点入度为 $0$，最优只保留最小权值点。
• 连通分量若非树（ $边数 ≥ 点数$ ），则存在方案使所有点 $入度 ≥ 1$，贡献为 $0$ 。
• 用并查集维护每个分量的点数、边数、最小点权。
• 合并时累加边数并更新最小权值，最后只累加树分量的最小权值。
• 时间复杂度 $O((n+m) α(n))$，空间 $O(n)$，适用于 $n,m ≤ 10^6$。

100pts

T3 删除滚木

依旧神秘标题，依旧神秘二分

依旧二分看不出来QwQ

一个max一个最小值可能对我这种蒟蒻来说还是太神秘了吧。。。于是就写了部分分

还有很奇怪的一点啊 我明明写的是 #3 和 #9~11 的部分分，为什么 #9 没A反而把 #19 A了

我是该说数据强呢还是水呢。。。

本题思路小总结：

• 二分答案 $x$，判断能否通过删除至多 $k$ 个数使剩余序列的任意相邻两项满足 $|a_j – a_i| ÷ (j – i) ≤ x$。
• 条件等价于 $a_j – x·j ≤ a_i – x·i 且 a_i + x·i ≤ a_j + x·j$，即对每对保留点 $(i, a_i)$，定义二元组 $(x·i – a_i, x·i + a_i)$。
• 若保留序列合法，则这些二元组需满足第一维非降且第二维非降，即二维偏序下的最长链长度。
• 对二元组按第一维排序，第二维求 LIS（非严格），得到可保留的最大点数 $len$。
• 若 $len ≥ n – k$，则 $x$ 可行，否则不可行，二分单调，精度 $1^{-10}$ 输出（为什么题面 $1^{-10}$ 数据 $1^{-15}$）。

20pts

订正

T4 午安。

怎么上次晚安这次午安，居然不按时间顺序排列，都不吸引读者了(bushi)

依旧是一个可恶的、难懂的（bushi，但本蒟蒻花了整整两分钟看这个公式QwQ）、一长串的、加神秘模数的数学公式

也是想不出来，直接线段树暴力了：（

本题思路小总结：

• 利用单调栈求出每个位置作为最大值/最小值的贡献区间，加、减运算分别累加最大值和与最小值和的差。
• 乘法运算采用分治：跨中点的区间，左端取最大/最小，右端维护最大/最小及前缀和，按最大值与最小值分界情况累加乘积。
• 除法（向下取整）与取模：枚举每个元素作为区间最小值，统计所有区间和 $S$，再对每个商值 $k$ 统计最小值为 $v$ 的区间中最大值落在 $[kv, (k+1)v – 1]$ 的个数。
• 用并查集维护当前已处理的最小值位置，快速求每个位置左右最近的已处理点，从而得到该值为最小值时的扩展区间。
• 离线按最大值上限分组询问，差值计数得到每个商对应的区间数，进而算出除法答案$（商×区间数）$和取模答案$（和 – 商×v×区间数）$。
• 最终五种结果分别输出：最大值和、最大值和与最小值和之差、最大最小乘积和、除法结果、取模结果。

20pts

订正