795 div.2 D. Max GEQ sum monotone stack

1691D
1800

The question

Give a sequence $a_1,a_2,...,a_n$, Ask if all $i,j(1\le i\le j\le n,)$, Satisfy $\max (a_i,...a_j)\ge a_i+...+a_j$.$(n\le 2e5,-10^9\le a_i\le 10^9)$

Ideas

It is observed that there is $n^2$ Species value , On the left side, there are at most $n$ Species value , So we consider from $1\to n$ enumeration $a_i$, And find an interval $[L,R]$ Satisfy $a_i$ Is the largest number , On this basis, maximize $\sum a[L,R]$.

First step , Find the corresponding $[L_i,R_i]$ Value range . That is, find the first greater than... On the left and right respectively $a_i$ Number of numbers , It can be realized by two monotone stacks . For example, when calculating the right side , Maintain a monotonically increasing stack , Traverse back and forth , If at present $a_i$ Greater than the value corresponding to the top element of the stack , The first position on the right side of the stack top element that is larger than it is $i$. Similar on the other side .
The second step , Maximize $\sum a[L,R]$. Just maintain a prefix and an array , And find $[L,i-1]$ And $[i,R]$ Subtract the maximum value in . You can use a segment tree or ST surface , Note that the prefix and array subscript are from 0 Start .

Code

int n, a[maxn], L[maxn], R[maxn];
int pre[maxn];
struct segment_tree {
    
	int l, r;
	int minn, maxx;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define mn(x) tree[x].minn
	#define mx(x) tree[x].maxx
}tree[maxn << 2];
void pushup(int p) {
    
	mn(p) = min(mn(p<<1), mn(p<<1|1));
	mx(p) = max(mx(p << 1), mx(p << 1 | 1));
}
void build(int p, int l, int r) {
    
	l(p) = l, r(p) = r;
	if(l == r) {
    
		mn(p) = mx(p) = pre[l];
		return;
	} 
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	pushup(p);
}
int query_min(int p, int l, int r) {
    
	if(l(p) >= l && r(p) <= r) {
    
		return mn(p);
	}
	int mid = (l(p) + r(p)) >> 1;
	int ans = (1ll<<62);
	if(l <= mid) ans = min(ans, query_min(p << 1, l, r));
	if(r > mid) ans = min(ans, query_min(p << 1 | 1, l, r));
	return ans;
}
int query_max(int p, int l, int r) {
    
	if(l(p) >= l && r(p) <= r) {
    
		return mx(p);
	}
	int mid = (l(p) + r(p)) >> 1;
	int ans = -(1ll<<62);
	if(l <= mid) ans = max(ans, query_max(p << 1, l, r));
	if(r > mid) ans = max(ans, query_max(p << 1 | 1, l, r));
	return ans;
}
void solve() {
    
    int last = 0;
    cin >> n;
    pre[0] = 0;
    for(int i = 1; i <= n; i++) {
    
    	cin >> a[i];
    	pre[i] = pre[i-1] + a[i];
    }
    a[n+1] = a[0] = INF;
    stack<int> s;
    for(int i = 1; i <= n + 1; i++) {
    
    	while(s.size() && a[s.top()] < a[i]) {
    
    		R[s.top()] = i;
    		s.pop();
    	}
    	s.push(i);
    }
    while(s.size()) s.pop();
    for(int i = n; i >= 0; i--) {
    
    	while(s.size() && a[s.top()] < a[i]) {
    
    		L[s.top()] = i;
    		s.pop();
    	}
    	s.push(i);
    }
    while(s.size()) s.pop();
	build(1, 1, n);
    for(int i = 1; i <= n; i++) {
    
    	int mnn = query_min(1, L[i], i-1);
    	if(L[i] == 0) mnn = min(mnn, 0LL);
    	int mxx = query_max(1, i, R[i] - 1);
    	if(mxx - mnn > a[i]) {
    
    		cout << "NO\n";
    		return;
    	}
    }
    cout << "YES\n";
}