codeforces 1556 E. Equilibrium (线段树)

题目链接:https://codeforces.com/contest/1556/problem/E

\(c[i] = a[i]-b[i]\),将对 \(a\) 的操作看作 \(+1\),对 \(b\) 的操作看作 \(-1\),奇数位加,偶数位减,可以想到括号序列,\(c[i]<0\),即为连续的左括号,\(c[i]>0\),即为连续的右括号,问题转化为每次可以删除括号序列中若干 \(()\),问最少需要删除几次

首先判断括号序列是否有解,维护 \(c[i]\) 的前缀和,要求 \(l\)\(r\) 的每个位置右括号均多于或等于左括号的数量,维护前缀和的区间最大值即可

如果有解,左括号累计最多的位置的左括号数量即为答案,因为此时每个左括号都不能同时被删除,且所有删除操作中都包含其中一个左括号

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 200010;
const ll INF = 1e18+7;

int n, q;
ll a[maxn], b[maxn], c[maxn], sum[maxn]; 
 
struct Node{
	ll mi, mx;
}t[maxn<<2];
 
void pushup(int i){
	t[i].mi = min(t[i<<1].mi, t[i<<1|1].mi);
	t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
}
 
void build(int i, int l, int r){
	if(l == r) {
		t[i].mi = t[i].mx = sum[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(i<<1, l, mid); build(i<<1|1, mid+1, r);
	pushup(i);
}

ll qmi(int i, int l, int r, int x, int y){
	if(x <= l && r <= y){
		return t[i].mi;
	} 
	int mid = (l + r) >> 1;
	ll res = INF;
	if(x <= mid) res = min(res, qmi(i<<1, l, mid, x, y));
	if(y > mid) res = min(res, qmi(i<<1|1, mid+1, r, x, y));
	return res;
}
 
ll qmx(int i, int l, int r, int x, int y){
	if(x <= l && r <= y){
		return t[i].mx;
	} 
	int mid = (l + r) >> 1;
	ll res = -INF;
	if(x <= mid) res = max(res, qmx(i<<1, l, mid, x, y));
	if(y > mid) res = max(res, qmx(i<<1|1, mid+1, r, x, y));
	return res;
}
 
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘){ s = s * 10 + ch - ‘0‘; ch = getchar(); } return s * f; }

int main(){
	n = read(), q = read();
	for(int i = 1 ; i <= n ; ++i) a[i] = read();
	for(int i = 1 ; i <= n ; ++i) b[i] = read();
	
	for(int i = 1 ; i <= n ; ++i) c[i] = a[i] - b[i];
	
	for(int i = 1 ; i <= n ; ++i) sum[i] = sum[i-1] + c[i]; 
//	for(int i = 1 ; i <= n ; ++i) printf("%d ", c[i]); printf("\n");
//	for(int i = 1 ; i <= n ; ++i) printf("%d ", sum[i]); printf("\n");
	
	build(1, 1, n);
	
	int l, r;
	for(int i = 1 ; i <= q ; ++i){
		l = read(), r = read();
		if(qmx(1, 1, n, l, r) <= sum[l-1] && qmx(1, 1, n, r, r) == sum[l-1]){
			printf("%lld\n", -(qmi(1, 1, n, l, r)-sum[l-1]));
		} else{
			printf("-1\n");
		}
	}
	
	return 0;
}

codeforces 1556 E. Equilibrium (线段树)

上一篇:Vue怎么引用组件和使用组件?


下一篇:ValueError: check_hostname requires server_hostname解决方案