跳转至

8081.【2024年SD省队集训 day2】反转了 (flip)

题意

给定长度为 \(N\) 的数组 \(A\)，定义 \(S_0 = 0\)，\(S_i = \sum_{j=1}^i A_j(i \in [1,N])\)。

对 \(K \in [0,N]\)，求解：

  • 至多反转 \(K\) 个元素的符号，求 \(\max_{i \in [0,N]} {S_i}\) 的最大值。

朴素解法

暴力枚举 \(K\)，并枚举 \(i \in [0,N]\)，假定 \(S_i = \max_{j \in [0,N]} {S_j}\)，显然最优方案为反转前 \(i\) 个元素中绝对值最大的 \(K\) 个元素。

设 \(B_i = \max(0,-A_i)\)，那么第 \(i\) 段前缀对 \(K\) 的贡献为 \(C(i,K) = S_i + 2 W(i,K)\)，其中 \(W(i,K)\) 为 \(\{B_1,B_2,\dots,B_i\}\) 中的前 \(K\) 大元素的和。

答案即为 \(\max{C(i,K)}\)。

注意当 \(i \lt K\) 时，\(W(i,K) = \sum_{j=1}^i B_j\)。

\(W(i,K)\) 可以用主席树在 \(O(\log N)\) 时间内求得。

总时间复杂度 \(O(N ^ 2 \log N)\)，期望得分 30。

优化

设 \(f_K\) 表示 \(\min \{i | \forall j,C(i,K) \ge C(j,K)\}\)，即使得 \(C(i,K)\) 最大的最小的 \(i\) 值。

容易发现 \(f\) 非严格单调递增。

于是便如 ABC348G 一样，用分治 + 主席树解决。

单调性证明

实践是检验真理的唯一标准 
 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
int n,a[N + 2];
long long s[N + 2];
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
    for(int i=1; i<=n; ++i) s[i]=s[i-1]+a[i];
    int lst=-1;
    for(int i=0; i<=n; ++i) {
        multiset<int> st;
        ll sum=0,ans=0,k=0;
        for(int j=1; j<=n; ++j) {
            if(i!=0&&a[j]<0&&(st.size()<i||*st.begin()<-a[j])) {
                if(st.size()==i) {
                    sum-=*st.begin();
                    st.erase(st.begin());
                }
                sum+=-a[j];
                st.insert(-a[j]);
            }
            if(s[j]+sum*2>ans) ans=s[j]+sum*2,k=j;
        }
        assert(lst<=k);
        lst=k;
        printf("%lld ",ans);
    }
    return 0;
}

考虑使用反证法，假设 \(\exists i,f_i > f_{i+1}\)，设 \(f_i = x,f_{i+1} = y\)。

因为 \(f_i = x\)，于是有

\[ \begin{aligned} & C(y,i) \lt C(x,i) \\ & S_y + 2W(y,i) \lt S_x + 2W(x,i) \\ & S_y - S_x + 2W(y,i) - 2W(x,i) \lt 0 \\ \end{aligned} \]

因为 \(f_{i+1} = y\)，于是有

\[ \begin{aligned} C(y,i+1) & \ge C(x,i+1) \\ S_y + 2W(y,i+1) & \ge S_x + 2W(x,i+1) \\ S_y - S_x + 2W(y,i+1) - 2W(x,i+1) & \ge 0 \\ & \gt S_y - S_x + 2W(y,i) - 2W(x,i)\\ W(y,i+1) - W(x,i+1) & \gt W(y,i) - W(x,i) \\ W(y,i+1) - W(y,i) & \gt W(x,i+1) - W(x,i) \\ \end{aligned} \]

这显然是矛盾的，因为 \(y<x\)，\(W(y,i+1) - W(y,i)\) 相当于 \(\{B_1,B_2,\dots,B_x\}\) 中的第 \(i+1\) 大的元素，但是 \(\{B_1,B_2,\dots,B_y\} \subset \{B_1,B_2,\dots,B_x\}\)，于是必有 \(W(y,i+1) - W(y,i) \le W(x,i+1) - W(x,i)\)，矛盾。

因此，\(f\) 是非严格单调递增的。

其他例题