Po7ed's Blog

本文字符串下标从 $1$ 开始，无歧义时默认 $n$ 为当前所述字符串长度。

联合省选 2025 总结

比赛情况

D1T1

思考 [1,1.5]h 无果，遂放弃。没有想到关键结论：最大化中位数必不劣。高估题目难度。

D1T2

约 1h 解决暴力，2h 左右疯狂卡常 + 乱搞，试图冲过 8e4，比较成功。约 88pts，但是用时过长。

D1T3

过难。

D2T1

思考约 1h，暴力写 + 调约 2h，写线段树 + 调约 1.5h。没调出来，与暴力同分。非常失败，原因是胡思乱想时间过长，写暴力能力（准确度）有待提升。

D2T2

暴力都难写。

D2T3

没时间看。

比赛经验较缺乏，习惯于长时间思考。应快速验证做法并在想清楚后实施，避免浪费时间。

将来计划

1. 复习已学算法和数据结构，巩固基础；
2. 练习 ARC 和 CF Div 1,2，练习观察性质和题目转化能力；
3. 学习省选算法，练习相应例题。

Tasks

cdq 分治、扩欧拉。

Problems

概率、构造、Ad-hoc、数数。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

调换枚举顺序

Example 1 求

$ans=\sum_{l=1}^{n}\sum_{r=l}^{n}\min_{l\le i\le r}a_i$

求 $\max$ 类似。直接统计十分困难，考虑枚举 $i$，求符合条件的区间数量。

$\begin{aligned} ans&=\sum_{i=1}^{n}\sum_{l=1}^{i}\sum_{r=i}^{n}[a_i=\min_{l\le j\le r}a_j]\\ &=\sum_{i=1}^{n}\sum_{l=1}^{i}\sum_{r=i}^{n}[\forall l\le j\le r,a_i\ge a_j]\\ \end{aligned}$

先假设 $a_i$ 互不相同，那么设 $pre_i$ 为最大的 $j$ 满足 $j<i\land a_j<a_i$，$nxt_i$ 为最小的 $j$ 满足 $j>i\land a_j<a_i$，那么 $l,r$ 必须满足 $pre_i<l\land r<nxt_i$。

不难发现，符合条件的 $[l,r]$ 数量即为 $(i-pre_i)(nxt_i-i)$。故

$ans=\sum_{i=1}^{n}(i-pre_i)(nxt_i-i)$

$pre,nxt$ 可用单调栈求，基本操作。

当 $a_i$ 中有相同元素时可能会算重或算漏，不妨钦定当且仅当 $i$ 为 $[l,r]$ 内第一个最小值时合法，那么需要稍微修改 $pre_i$ 的定义，为最大的 $j$ 满足 $j<i\land a_j\le a_i$，即 $i$ 之前不能有相等的最小值。

Example 2 求

$ans=\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r)$

其中 $f(l,r)$ 表示 $S(l,r)=\{a_i\mid i\in [l,r]\}$ 中的连续段个数。（Src：AT_abc390_f [ABC390F] Double Sum 3。）

注意到每个连续段必有结尾（或者开头，也是等价的），故使 $[l,r]$ 内每个 $a_x$ 均代表一个连续段，其中 $x$ 满足 $x$ 最小且 $a_x\in S(l,r)\land a_x+1\notin S(l,r)$。

枚举 $x$，求有多少个区间 $[l,r]$ 满足 $S(l,r)$ 中有 $a_x$ 代表的连续段。同样定义 $pre_i$ 为最大的 $j$ 使得 $j<i\land(a_j=a_i\lor a_j=a_i+1)$，$nxt_i$ 为最小的 $j$ 使得 $j>i\land a_j=a_i+1$，答案与上一题形式相同。

Conclusion 本质是将枚举复杂度大的对象换成复杂度小的。比如区间有 $O(n^2)$ 个，而最小值只可能有 $O(n)$ 个，显然枚举最小值更优。但同时也要考虑求合法对应对象的复杂度。最小值求合法区间数量均摊 $O(1)$，可以接受。

对数

对数是乘方的逆运算，与除是乘的逆运算类似。所以，所有对数的性质及推导过程都可以类比除法。

长文警告。显然的性质略去不写或不证。

本文研究数论，故所有字母默认代表整数。