题解：P11064 【MX-X4-T4】「Jason-1」一步最优

qfy123 · 2024-09-25 19:55:21 · 题解

P11064

Update on 2025.8.6：大修。

传送门

前置知识：线段树维护动态区间最大子段和以及一道例题。

思路

分析

首先有个贪心策略是显然的：当要使这个算法得到的答案最大时，每次取元素之和最大的区间中长度最短的那个区间；反之，每次取元素之和最大的区间中长度最长的那个区间。这很显然，因为每次增加值是 \ge 0 的，所以在求最大或最小值时要尽量使选择次数多或少。

然后有个结论：在按照上述贪心选择的过程中，每次选择的区间一定是不交的，即，前面选择的区间不会影响后面的区间。

为何？试着证明一下：

假设能够在多个元素之和最大的区间中任取两个不同的区间 [l_1,r_1] 和 [l_2,r_2]，满足这两个区间有交而无包含关系，即 l_1 < l_2, r_1 < r_2。

设他们的交为 [l,r]，记 S = s_{l_1,r_1} = s_{l_2,r_2}，现在考虑区间 [l_1,r_2]，根据容斥原理，s_{l_1,r_2} = 2S - s_{l,r}，而根据假设，S \ge s_{l,r}。综上 s_{l_1,r_2} \ge S。

对于 s_{l_1,r_2} > S 的情况，与原假设矛盾，显然是选择 [l_1,r_2] 更好。

对于相等的情况，不难发现，[l,r] 的长度一定比区间 [l_1,r_1] 和 [l_2,r_2] 短，[l_1,r_2] 的长度一定比区间 [l_1,r_1] 和 [l_2,r_2] 的长。那么对于贪心策略而言，一定是优先考虑 [l,r] 或 [l_1, r_2]。

所以说无论如何，假设在一次选择中出现了一对相交而不包含的极大区间，那么一定会有更优的答案（区间的交或并），而像这样的有交集的区间会被排除，最终每次选择的区间就是无交集的了。

做法

有了这个结论，这道题就变成线段树维护动态区间最大子段和板子的加强版了。相比于板子题，这道题多了维护整个数组的所有的最大子段和中，长度最短和长度最长的区间最大子段和的左右端点。

那如何维护呢？其实就是在上传的时候分讨即可。如果不想分讨，也可以自己写一个比较函数来减小代码难度。

最后再说一下用完一个区间怎么处理的问题。其实就只要给这个区间的每个点的值改成 -inf。发现均摊下来每个点最多被修改一次，因此每次暴力单点修改即可。关于 -inf 的取值，由于 - 10 ^ 9 \times 10 ^ 5 = - 10 ^{14}，并且要防止爆 long long。综上，-inf 的取值最好是 -10^{14}。

Code

#include<bits/stdc++.h>
#define int long long 
#define ull unsigned long long
#define ri register int
#define rep(i,j,k) for(ri i=(j);i<=(k);++i) 
#define per(i,j,k) for(ri i=(j);i>=(k);--i)
#define repl(i,j,k,l) for(ri i=(j);(k);i=(l))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pc(x) putchar(x)
#define fir first
#define se second 
#define MP pair<int,int>
#define PB push_back
#define lson p << 1
#define rson p << 1 | 1
using namespace std;
char BUFFER[100000],*P1(0),*P2(0);
#define gtc() (P1 == P2 && (P2 = (P1 = BUFFER) + fread(BUFFER,1,100000,stdin), P1 == P2) ? EOF : *P1++)
inline int R(){
    int x;char c;bool f = 0;
    while((c = gtc()) < '0') if(c == '-') f = 1;
    x = c ^ '0';
    while((c = gtc()) >= '0') x = (x << 3) + (x << 1) + (c ^ '0');
    return f?(~x + 1):x;
}
inline void O(int x){
    if(x < 0) pc('-'),x = -x;
    if(x < 10) pc(x + '0');
    else O(x / 10),pc(x % 10 + '0');
}
inline void out(int x,int type){
    if(type == 1) O(x),pc(' ');
    if(type == 2) O(x),pc('\n');
    if(type == 3) O(x);
}
inline void OI(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
const int N = 2e5 + 10;
const int inf = 1e14;
struct S{
    int l, r, val;
};
//重写比较函数，避免分讨
S gmx1(S a, S b){
    if(a.val == b.val) return a.r - a.l > b.r - b.l? b : a;
    return a.val > b.val? a : b;
} 
S gmx2(S a, S b){
    if(a.val == b.val) return a.r - a.l < b.r - b.l? b : a;
    return a.val > b.val? a : b;
}

struct Tr{
    int l, r, sum;
    S mx, lmx, rmx;
}t1[N << 2],t2[N << 2];//t1：维护这种贪心方法所能取到的最大值，t2反之
int a[N],n,T,ans;
//pushup 大体和维护区间最大子段和是相同的，不做过多阐述
void pushup1(int p){
    t1[p].sum = t1[lson].sum + t1[rson].sum;
    t1[p].lmx = gmx1(t1[lson].lmx, (S){t1[lson].l, t1[rson].lmx.r, t1[lson].sum + t1[rson].lmx.val});
    t1[p].rmx = gmx1(t1[rson].rmx, (S){t1[lson].rmx.l, t1[rson].r, t1[rson].sum + t1[lson].rmx.val});
    t1[p].mx = gmx1(gmx1(t1[lson].mx, t1[rson].mx), (S){t1[lson].rmx.l, t1[rson].lmx.r, t1[lson].rmx.val + t1[rson].lmx.val});
}
void pushup2(int p){
    t2[p].sum = t2[lson].sum + t2[rson].sum;
    t2[p].lmx = gmx2(t2[lson].lmx, (S){t2[lson].l, t2[rson].lmx.r, t2[lson].sum + t2[rson].lmx.val});
    t2[p].rmx = gmx2(t2[rson].rmx, (S){t2[lson].rmx.l, t2[rson].r, t2[rson].sum + t2[lson].rmx.val});
    t2[p].mx = gmx2(gmx2(t2[lson].mx, t2[rson].mx), (S){t2[lson].rmx.l, t2[rson].lmx.r, t2[lson].rmx.val + t2[rson].lmx.val});
}
void build(int l, int r, int p, int mode){//mode = 1：处理最大值情况；mode = 2：处理最小值情况
    if(mode == 1){
        t1[p].l = l, t1[p].r = r;
        if(l == r){
            t1[p].sum = a[l];
            t1[p].mx = t1[p].lmx = t1[p].rmx = (S){l,l,a[l]};
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, lson, mode);
        build(mid + 1, r, rson, mode);
        pushup1(p);
    }else{
        t2[p].l = l, t2[p].r = r;
        if(l == r){
            t2[p].sum = a[l];
            t2[p].mx = t2[p].lmx = t2[p].rmx = (S){l,l,a[l]};
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, lson, mode);
        build(mid + 1, r, rson, mode);
        pushup2(p);     
    }
}
void modify(int l, int r, int p, int v, int mode){
    if(mode == 1){
        if(l == r){
            t1[p].sum = -inf;
            t1[p].rmx.val = t1[p].lmx.val = t1[p].mx.val = -inf;
            return;
        }
        int mid = (l + r) >> 1;
        if(v <= mid) modify(l, mid, lson, v, mode);
        else modify(mid + 1, r, rson, v, mode);
        pushup1(p);     
    }else{
        if(l == r){
            t2[p].sum = -inf;
            t2[p].rmx.val = t2[p].lmx.val = t2[p].mx.val = -inf;
            return;
        }
        int mid = (l + r) >> 1;
        if(v <= mid) modify(l, mid, lson, v, mode);
        else modify(mid + 1, r, rson, v, mode);
        pushup2(p);         
    }
}
signed main(){
    T = R();
    while(T--){
        n = R();
        rep(i, 1, n) a[i] = R();
        build(1, n, 1, 1);build(1, n, 1, 2);
        rep(i, 1, n){
            S x = t1[1].mx;//答案在线段树根结点处取得
            if(x.val > 0){
                ans += x.val;
                rep(j, x.l, x.r) modify(1, n, 1, j, 1);//每个点至多修改一次，因此暴力单点修改即可
            }
            out(ans, 1);
        }
        pc('\n'); ans = 0;
        rep(i, 1, n){
            S x = t2[1].mx;
            if(x.val > 0){
                ans += x.val;
                rep(j, x.l, x.r) modify(1, n, 1, j, 2);
            }
            out(ans, 1);
        }
        pc('\n'); ans = 0;
    }
    return 0;
}