自动搬运

查看原文

来自洛谷，原作者为

	qfy123 不拿勾7不改签

搬运于2025-08-24 23:03:56，当前版本为作者最后更新于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;
}