CF1359D Yet Another Yet Another Task

貌似没有线段树做法。

记\(s\)为\(a\)的前缀和数组。

对于一个确定的右端点 \(r\) 和左端点 \(l\)，它对于答案的贡献是 \(s_r-s_{l-1}-max\{a_i\},l\le i\le r\) ，如果枚举右端点，令 \(c_l=s_{l-1}+max\{a_i\},l\le i\) 。那么其实就是要求 \(1\le k\le r-1\) 的 \(min\{c_k\}\)。

线段树维护 \(c_k\) 即可。

用单调栈求出 \(a_i\) 左边第一个大于自己的数 \(a_p\)，然后把 \([p,i-1]\) 的 \(max\{a_i\}\) 覆盖成 \(a_r\) 即可。

然后你发现要维护 \(c\) ，你得维护 \(s\) 的最小值，和 \(max\{a_i\}\) 。

时间复杂度 \(O(nlogn)\) 。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n, s[N];
int stk[N], top;

struct Node {
	int l, r;
	int s, a, v; // s[i] + a[i]
	int tag;
}tr[N << 2];

void pushup(int u) {
	tr[u].v=min(tr[u<<1].v,tr[u<<1|1].v);
	tr[u].s=min(tr[u<<1].s,tr[u<<1|1].s);
}

void pushdown(int u) {
	if (tr[u].tag != 2e9) {
		tr[u<<1].a=tr[u].tag,tr[u<<1].v=tr[u<<1].s+tr[u].tag;
		tr[u<<1|1].a=tr[u].tag,tr[u<<1|1].v=tr[u<<1|1].s+tr[u].tag;
		tr[u<<1|1].tag=tr[u<<1].tag=tr[u].tag;
		tr[u].tag = 2e9;
	} 
}

void build(int u,int l,int r) {
	tr[u]={l,r};
	tr[u].tag=2e9;
	if (l==r) {
		tr[u].a=1e9;
		tr[u].s=s[l];
		tr[u].v=tr[u].a+tr[u].s;
		tr[u].tag=2e9;
		return;
	}
	int mid = l +r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}

void modify(int u,int L,int R,int k) {
	if (tr[u].l>=L&&tr[u].r<=R) {
		tr[u].a=k;
		tr[u].v=tr[u].s+k;
		tr[u].tag=k;
		return ;
	}
	int mid=tr[u].l+tr[u].r>>1;
	pushdown(u);
	if (L<=mid) modify(u<<1,L,R,k);
	if (R>mid) modify(u<<1|1,L,R,k);
	pushup(u);
}

int query(int u,int L,int R) {
	if (tr[u].l>=L&&tr[u].r<=R) 
		return tr[u].v;
	int mid=tr[u].l+tr[u].r>>1;
	pushdown(u);
	int res=2e9;
	if (L<=mid) res=min(res,query(u<<1,L,R));
	if (R>mid) res=min(res,query(u<<1|1,L,R));
	return res;
}

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 ans = 0;
	build(1,0,n);
	for (int i = 1; i <= n; i ++ ) {
		while (top && a[stk[top]] <= a[i]) top -- ;
		// [stk[top], i-1]拍成 a[i]+s[k]
		modify(1,stk[top],i-1,a[i]);
		ans=max(ans,s[i]-query(1,0,i-1));
		stk[ ++ top] = i;
	}
	cout << ans << endl;
	return 0;
}