Codeforces 刷题 2025.08.22

2126G1 - Bigs Wins (Easy Version)

考虑到 $a_i$ 值域较小，考虑 $V\times O(n)$ 或者 $V\times O(n\log n)$ 的做法。于是可以想到一个经典的转化：枚举中位数 $\texttt{med}$，令

这样就有 $\text{median}(a[l,r])\ge \texttt{med} \iff \sum_{i\in [l,r]} b_i\ge 0$.

固定了 $\texttt{med}$ 后，我们希望最大化答案，即找到 $[l,r]$ 使得 $\text{median}(a[l,r])\ge \texttt{med}$ 且 $\min a[l,r]$ 最小.

这里有一个非常精彩的转化。比如说 $[l,r]$ 这个区间已经固定了，那么

所以，这里衍生出两种做法：

1. （左式衍生做法）枚举区间，然后在区间内找最小值。这个就是非常经典的序列处理办法了，用数据结构维护左端点，然后把右端点放到数据结构里查。这里，我们只需要对某个右端点 $r$，找到 leftmost $l$ 使得 $\sum_{i\in[l,r]} b_i\ge 0$ 然后找出 $\min_{i\in [l,r]} a_i$ 即可.
2. （右式衍生做法）枚举 $a_i$，对 $a_i$ 检查是否有一个区间 $[l,r]$ 包含了 $a_i$ 且且中位数 $\ge \texttt{med}$。只需要找能包含 $a_i$ 的最长区间即可，所以我们可以在计算 $b_i$ 前缀和 $p_i$ 的基础上，维护 $p_i$ 的 prefix min 与 suffix max 即可。只要 suffix max $-$ prefix min $\ge 0$，那么 suffix max 和 prefix min 之间的所有 $a_i$ 就都会被计算一边，能确保答案不漏。

第一种做法理论也可行。但是我的实现是 $O(Vn\log^2 n)$ 显然会被卡 -_- 所以还是得用第二种方法，时间复杂度是 $O(Vn)$ 的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>
constexpr int N = 2e5 + 10;

int n;
std::array<int, N> a, prefix, minpre, maxsuf;

void mark(int m) {
    for (int i = 1; i <= n; i++) 
        prefix[i] = prefix[i - 1] + (a[i] < m ? -1 : 1);
    
    minpre[0] = 0;
    for (int i = 1; i <= n; i++)
        minpre[i] = std::min(minpre[i - 1], prefix[i]);
    
    maxsuf[n] = prefix[n];
    for (int i = n - 1; i >= 1; i--) 
        maxsuf[i] = std::max(maxsuf[i + 1], prefix[i]);
}

void run() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    int ans = 0;
    for (int med = 100; med >= 0; med--) {
        mark(med);
        for (int i = 1; i <= n; i++) {
            if (maxsuf[i] >= minpre[i - 1]) 
                ans = std::max(ans, med - a[i]);
        }
    }

    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
    
    int t;
    std::cin >> t;
    while (t--) run();
}