整个活，水一发线段树题解

#include<bits/stdc++.h>
#define ls x<<1
#define rs x<<1|1
using namespace std;
typedef long long ll;
ll n,q,a[1000005];
struct sb{
	long long minn;
	long long maxx;
	long long ans;
}sum[4000005];
void build(ll x,ll l,ll r){
	if(l==r){
		sum[x].minn=sum[x].maxx=a[l];
		sum[x].ans=-1e9;
		return;
	}
	ll mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
	sum[x].minn=min(sum[ls].minn,sum[rs].minn);
	sum[x].maxx=max(sum[ls].maxx,sum[rs].maxx);
	sum[x].ans=max(max(sum[ls].ans,sum[rs].ans),sum[rs].maxx-sum[ls].minn);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	cout<<sum[1].ans<<endl;
}