2024-1-12 DAY3

D - Max GEQ Sum

经典线段树调几个小时

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e5 + 10;
int a[N];
int ll[N],rr[N];
int pre[N];
int n;

struct node
{
	int l,r;
	int Max;
	int Min;
}segTree[N*3];

void build(int i,int l,int r){
	segTree[i].l = l;
	segTree[i].r = r;
	segTree[i].Max = 0;
	if(l==r) return;
	int mid = l + r >> 1;
	build(i<<1,l,mid);
	build((i<<1)|1,mid+1,r);
}

//更新第k个值为val
void update(int i,int k,int val){
	if(segTree[i].l == k && segTree[i].r == k){
		segTree[i].Max = segTree[i].Min = val;
		return;
	}
	int mid = (segTree[i].l + segTree[i].r) >> 1;
	if(k <= mid) update(i<<1,k,val);
	else		 update((i<<1)|1,k,val);
	
	segTree[i].Max = max(segTree[i<<1].Max,segTree[(i<<1)|1].Max);
	segTree[i].Min = min(segTree[i<<1].Min,segTree[(i<<1)|1].Min);
}

pair<int,int> query(int i,int l,int r){
	if(segTree[i].l >= l &&segTree[i].r <= r)
		return {segTree[i].Min,segTree[i].Max};
	int mid = (segTree[i].l + segTree[i].r) >> 1;
	if(r<=mid) return query(i<<1,l,r);
	else if(l>mid) return query((i<<1)|1,l,r);
	else{
		auto [a1,b1] = query(i<<1,l,mid);
		auto [a2,b2] = query(i<<1|1,mid+1,r);
		return {min(a1,a2),max(b1,b2)}; 
	}
}

void solve()
{
 	cin >> n;
 	for(int i=1;i<=n;i++)
 	{
 		cin >> a[i];
 		pre[i] = pre[i-1] + a[i];
 	}
 	stack<int> path;
 	a[0] = 1e10;
 	a[n+1] = 1e10;
 	for(int i=1;i<=n+1;i++)
 	{
 		if(path.empty()) path.push(i);
 		else{
 			if(a[i]<=a[path.top()]) path.push(i);
 			else{
 				while(path.size()&&a[i]>a[path.top()])
 				{
 					int x=path.top();
 					rr[x] = i;
 					path.pop();
 				}
 				path.push(i);
 			}
 		}
 	}
 	while(path.size()) path.pop();
 	for(int i=n;i>=0;i--)
 	{
 		if(path.empty()) path.push(i);
 		else{
 			if(a[i]<=a[path.top()]) path.push(i);
 			else{
 				while(path.size()&&a[i]>a[path.top()])
 				{
 					int x=path.top();
 					ll[x] = i;
 					path.pop();
 				}
 				path.push(i);
 			}
 		}
 	}
 	
 	build(1,0,n);
 	for(int i=0;i<=n;i++) update(1,i,pre[i]);

 	for(int i=1;i<=n;i++)
 	{
 		auto [a1,b1] = query(1,ll[i],i-1);
 		auto [a2,b2] = query(1,i,rr[i]-1);
 		// cout << i <<endl;
 		// cout << ll[i] << " " << rr[i] <<endl;
 		if((pre[i-1]-a1>0) || (b2-pre[i]>0))
 		{
 			//cout << i <<endl;
 			cout << "NO" <<endl;
 			return;
 		}
 		// cout << i <<endl;
 		// cout << a1 << " " << b1 << endl;
 		// cout << a2 << " " << b2 << endl;
 		// cout << pre[i-1] << " " << pre[i] <<endl;
 	}
 	cout << "YES" <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

C - Water the Trees

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 3e5 + 10;
int h[N];
int n;
int maxx = 0;
bool check(int time){
	int x = time / 2; //偶数
	int y = time - x; //奇数
	for(int i=1;i<=n;i++){
		int len = maxx - h[i];
		int z = min(len/2,x);
		x -= z;
		len -= 2*z;
		z = min(len,y);
		y -= z;
		len -=z;
		if(len!=0) return false;
	}
	return true;
}

void solve()
{
 	int r = 1e18;
 	int l = 0;
 	maxx = 0;
 	int ans = 1e18;
 	cin >> n;
 	for(int i=1;i<=n;i++)
 	{
 		cin >> h[i];
 		maxx = max(maxx,h[i]);
 	}
 	while(l<=r){
 		int mid = l + r >> 1;
 		if(check(mid)){
 			r = mid - 1;
 			ans = min(ans,mid);
 		}else l = mid + 1;
 	}
 	l = 0;
 	r = 1e18;
 	maxx++;
  	while(l<=r){
 		int mid = l + r >> 1;
 		if(check(mid)){
 			r = mid - 1;
 			ans = min(ans,mid);
 		}else l = mid + 1;
 	}
 	cout << ans <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

今天偷个懒