[P9461 众数 II] 题解
larsr
·
·
题解
题目含义
用 a 生成 b，从 a_1 到 a_n 这样遍历，在 b 后面加入 1, 2, \ldots, a_i。比如样例 1，a = [1, 2, 3]。
-
a_1 = 1$，所以此时 $b = [1]
-
a_2 = 2$，所以此时 $b = [1, 1, 2]
-
a_3 = 3$，所以此时 $b = [1, 1, 2, 1, 2, 3]
假设 b 的长度为 m，最后输出：
\sum_{1 \leq l \leq m} \sum_{l \leq r \leq m} f(l, r)
这里的 f(l, r) 是 b 的区间 [l,r]，中最小众数（所有出现次数最大的数的最小值）。
暴力算法
计算出 b，再对 b 的每个区间计算最小众数，时间复杂度 O((\sum a_i)^3)。
计算 [l, r + 1] 时，其中的 [l, r] 已经算过了，所以算完 [l, r] 把 r + 1 算进去就可以了，时间复杂度 O((\sum a_i)^2)，得 30 分。
定理 1
定理：一个区间 [l,r] 的最小众数为 i（i 不为 1）,那么 b_l 一定是 i。
用反正法想，加入 b_l 不是 i，那么当 b_j = i 时，b_{j - 1} 一定是 i - 1。因为 i 不为 1，并且 b 是按照 1,2,\ldots 的顺序加入的。
通过这可以知道当 b_l 不是 i 时，这个区间出现一个 i，一定会出现一个 i - 1，所以：
\sum_{l \leq i \leq r}[b_i = i] \leq \sum_{l \leq i \leq r}[b_i = i - 1]
又因为 i 不为 1，而且 i - 1 \le i，这时 i - 1 就会成为这个区间的最小众数。所以定理成立。
定理 2
定理：一个区间 [l,r] 的最小众数为 i（i 不为 1），那么在这个区间中出现了的每个组中在区间出现了的数一定有一个为 i。
为方便讲述，下文对于 b 的表示类似于 [[1],[1,2],[1,2,3]]。
组的定义如下：
对于 a_i 会对 b 加入 1,2,\ldots,a_i，是同一个 a_i 加入的为一组，比如 b = [[1],[1,2],[1,2,3]]，第一组为 [1]，第二组为 [1,2]，第三组为 [1,2,3]。
这个定理可能有点长，看不懂，先给大家断一个句：在“这个区间”中“出现了的每个组”中“在区间出现了的数”一定有“一个为 i”。
比如 b = [[1],[1,2],[1,2,3]]，区间为 [3,6]，这里出现了的组有第二组和第三组，第二组中在区间出现了的数有 2，第三组中在区间出现了的数有 1,2,3。
第一个在区间出现了的组中在区间出现了的数中一定没有 1，因为定理 1(b_l = i)，而且 1 在每个组的最前面。
其他在区间出现了的每个组中在区间出现了的数中一定有 1，因为 1 是每个组第一个，假如这个组（不是第一个出现的组）在区间出现过，那么这个组一定出现了 1。
假设 p 是在区间出现了的组的数量，通过上面可以知道，1 在区间里出现的数量为 p - 1。要想让 i 成为这个区间的最小众数，就要让 i 出现次数比 1 多，因为一个组不可能出现同一个数，那么 i 出现次数为 p，所以定理成立。
定理 3
定理：一个区间 [l,r] 的最小众数为 i（i 不为 1），如果第 j 组在区间出现，那么 i \leq a_j。
根据定理 2，每个组要想其中的数 i 在区间里出现，那么首先要保证这个组有 i 这个数。要想有就要保证 i \leq a_j。
定理 4
定理：一个区间 [l,r] 的最小众数为 i（i 不为 1），那么 i \leq b_r。
根据定理 2，那么最后出现的组中 i 一定出现了。i 出现了，所以 r 必须比这个 i 的位置靠后，又不能靠后到下一个组，所以 i \leq b_r。
按值查找区间个数
我们可以换个思路，答案可以是：
\sum_{1 \leq i \leq \max a_i} P(i) \times i
一个区间 $[l,r]$ 要满足以上的四个定理，那么 $f(l,r) = i$，所以直接按这四个定理找就行。对于每个 $i$，首先枚举开头在哪个组，在接着枚举结尾在哪个组。时间复杂度 $O(n^2\max a_i)$ 核心代码：
```cpp
ll ans = 0;
for(ll i = 2; i <= 1e6; i++)
{
ll la = ans;
for(ll j = 1; j <= n; j++)
for(ll k = j; k <= n && a[k] >= i; k++)
ans = (ans + a[k] - i + 1) % mod;
if(la != ans)break;
}
```
细心的你可能发现了没有求 $1$。直接求 $1$ 的区间数量会很麻烦，我们可以用 `ci` 记录其他数的区间数量，最后用总区间数量减去它们就可以。代码如下：
```cpp
ll sum = 0;
for(int i = 1; i <= n; i++)sum = (sum + a[i]) % mod;
if(sum&1)sum = sum % mod * ((sum + 1) / 2) % mod;
else sum = (sum / 2) % mod * (sum + 1) % mod;
ans = (ans + sum - ci + mod) % mod;
```
假如你细心看上面的代码，你会发现每次对 `ans` 的操作都是 `ans = (ans + a[k] - i + 1) % mod;`，只和 `a[k]` 和 `i` 有关。我们可以直接枚举 `a[k]` 要算几次，乘一下就行了，次数是前面和 $a_k$ 连着的 $i \leq a_j$ 有几个。详细看一下解释：
> 比如 $a = [2, 1, 2, 2, 3, 2], i = 2,k = 5$，前面的保证 $i \leq a_j$，为 $a_1,a_3,a_4,a_5$（当然是要包括 $a_k$ 本身的），其中和 $a_k$ 连着的是 $a_3,a_4,a_5$。
时间复杂度为 $o(n\max a_i)$，预期得 70 分，核心代码如下：
```cpp
for(ll i = 2; i <= 1e6; i++)
{
ll la = ci;
for(ll j = 1; j <= n; j++)
{
if(a[j] < i)continue;
ll k = j;
while(a[k + 1] >= i)k++;
for(ll h = j; h <= k; h++)
ci = (ci + (a[h] - i + 1) * (h - j + 1)) % mod, ans = (ans + (a[h] - i + 1) * (h - j + 1) % mod * i) % mod;
j = k;
}
if(ci == la)break;
}
```
## 优化
把上面的思路，转换一下。可以把 $i \leq a_k$ 连起来的区间提出来。比如区间 $[l,r]$，对于 $l \leq k \leq r$，保证 $i \leq a_k$，并且 $a_{l - 1},a_{r + 1} < i$。提出到 $h$ 里面，$h_i = a_{i + l - 1}$。这个区间的子区间中最小众数为 $i$ 的数量为：
$$\sum_{1 \leq j \leq r - l + 1} (h_j - i + 1) \times j$$
即
$$\begin{pmatrix} \sum_{1 \leq j \leq r - l + 1} h_j \times j\end{pmatrix} - (i - 1) \frac{(l + r - 1)(l + r)}{2}$$
我们可以让 $i$ 从大往小遍历，在遍历一个数时，就要加入 $a_j = i$ 的数，新加入一个数可能要和之前的区间，假如 $i \leq a_{j - 1}$，那么把 $a_j$ 和 $a_{j - 1}$ 所在的区间合并。$a_{j + 1}$ 的操作也同样。区间合并可以用并查集操作。
确实合并完了，但对答案的贡献还没有更新。对于两个要合并的区间，分别是 $x_1,\ldots,x_{nx}$ 和 $y_1,\ldots,y_{ny}$（$x$ 在左，$y$ 在右），则：
$\sum_{1 \leq j \leq r - l + 1} h_j \times j = \sum_{1 \leq j \leq nx} x_j \times j + \sum_{1 \leq j \leq ny} y_j \times j + nx\sum y_j
我们用 now 记录所有区间 \sum_{1 \leq j \leq r - l + 1} h_j \times j 的和，等式右边前两项不用管了，因为已经记录过了，只需要让 now 增加 nx\sum y_j 就可以了。
对于 (i - 1) \frac{(l + r - 1)(l + r)}{2}，我们用 ji 记录所有区间 \frac{(l + r - 1)(l + r)}{2} 的和，每个区间用 siz 记录长度，合并的时候重新算一下就可以。
当 a_k = i 的数加入了，并且和其他区间合并完毕，要对答案计算贡献 ans = (ans + (now - ji * (i - 1) % mod + mod) % mod * i) % mod;。时间复杂度 O(n + \max a_i)。
code
#include<cstdio>
#include<algorithm>
#define N 1000010
#define mod 998244353
#define ll long long
using namespace std;
struct node
{
ll a;
int id;
}p[N];
int n;
int f[N], v[N];
ll now = 0, ji = 0, sum[N], siz[N], ci = 0, ans = 0;
bool cmp(node x, node y)
{
return x.a < y.a;
}
int find(int x)
{
if(f[x] == x)return x;
return f[x] = find(f[x]);
}
void uni(int x, int y)
{
if(siz[x] > siz[y])swap(x, y);
f[x] = y;
siz[y] += siz[x];
sum[y] = (sum[y] + sum[x]) % mod;
}
ll lon(ll x)
{
if(x & 1)return x * ((x + 1) / 2) % mod;
return (x / 2) * (x + 1) % mod;
}
void hb(int x, int y)
{
ji = (ji - lon(siz[x]) % mod - lon(siz[y]) % mod + lon(siz[x] + siz[y]) % mod + 2 * mod) % mod;
now = (now + sum[y] * siz[x]) % mod;
uni(x, y);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)scanf("%lld", &p[i].a), p[i].id = i;
for(int i = 1; i <= n; i++)f[i] = i, siz[i] = 1;
sort(p + 1, p + 1 + n, cmp);
int j = n;
for(ll i = 1e6; i > 1; i--)
{
while(p[j].a == i)
{
v[p[j].id] = 1;
sum[p[j].id] = p[j].a;
ji = (ji + 1) % mod;
now = (now + p[j].a) % mod;
if(v[p[j].id - 1])hb(find(p[j].id - 1), find(p[j].id));
if(v[p[j].id + 1])hb(find(p[j].id), find(p[j].id + 1));
j--;
}
ci = (ci + now - ji * (i - 1) % mod + mod) % mod;
ans = (ans + (now - ji * (i - 1) % mod + mod) % mod * i) % mod;
}
ll sum = 0;
for(int i = 1; i <= n; i++)sum = (sum + p[i].a) % mod;
sum = lon(sum);
ans = (ans + sum - ci + mod) % mod;
printf("%lld\n", ans);
return 0; \\完结撒花
}
结语
本人 2021 年开始学 OI，学了两年多，现在是准初二。最开始是在学而思学，2021CSP-J 考砸了，才考了 160。后来我认为培训机构教的太慢，就开始自学。
小升初的时候，父母为了给我一个更好的教育资源，把我送进了 TCMS。我在这个学校是借读，因为这个学校在之前干过教育局不让干的事（上网搜一下就知道了）。去年我 CSP 报的考点在北京，但进考场需要七天一直在京，所以我去年没考成，不然我就不是绿标了，早成蓝标了。
一次没考是不至于难过的，我真正难过的是我的处境。首先我是借读，所以我是没有学籍，在河北和北京报 CSP 好像都要通过学籍所在校，而且要想有学籍，就要把户口转过来，需要很长时间。也就是说假如我继续在这里上的话，今年又不能参加 CSP。
虽然我的 whk 已经不错了，但是父母就像被洗脑了一样，说：“你暑假不弯道，到时候就倒数了”。就这样我学 OI 的时间就这样一点一点被挤没。我是 B 类生，想考衡中，衡二太难了，只能考一个还行的高中。在还行的高中，想拿银牌，金牌太难了。简单来说，在那里上学的话，OI 也没什么用了。
TCMS 已经是一种畸形的教育了。老师只照顾私下收了钱的学生，体罚，打人的情况也有，每天都是死学。这种环境我实在是受不了。
我其实不只有这一条路，我的户口在广东，选择那里肯定比这好，我这次比赛考了第十，虽然和那些大佬比不了，但也不错，我要是有充足的时间，拿个银牌应该可以。
但是父母就是不同意，我和他们说我的想法，他们就训我一顿，后来我也不敢说了。我每天只能活在伤心和迷茫之中。我能有什么办法呀？只能放弃 OI 了……。