2020-03-04 10:55:53

# 正文

## 代码

#include <bits/stdc++.h>
#define ls num<<1
#define rs num<<1|1
using namespace std;
typedef long long ll;
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
template<typename T>void write(T x){
if(x<0)putchar('-'),x*=-1;
if(x>9)write(x/10);
putchar(x%10+48);
}
template<typename T>void writen(T x){
write(x);
puts("");
}
const int MAXN=5e4+10;
struct Tree{
int l,r;
ll lans,rans,sum,ans,max,min;
}t[MAXN*4];
int a[MAXN],x,y,n,T,T_,l1,r1,l2,r2;
ll s[MAXN];
Tree pushup(Tree L,Tree R){
Tree z;
z.sum=L.sum+R.sum;
z.lans=max(L.lans,L.sum+R.lans);
z.rans=max(R.rans,R.sum+L.rans);
z.ans=max(max(L.ans,R.ans),L.rans+R.lans);
z.max=max(L.max,R.max);
z.min=min(L.min,R.min);
z.l=L.l;z.r=R.r;
return z;
}
void build(int l,int r,int num){
if(l==r){
t[num].l=l;
t[num].r=r;
t[num].sum=a[l];
t[num].lans=a[l];
t[num].rans=a[l];
t[num].ans=a[l];
t[num].max=s[l];
t[num].min=s[l]-a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
t[num]=pushup(t[ls],t[rs]);
}
Tree query(int num){
if(x<=t[num].l&&t[num].r<=y)return t[num];
if(t[rs].l>y)return query(ls);
if(t[ls].r<x)return query(rs);
return pushup(query(ls),query(rs));
}
ll Max(int num){
if(t[num].l>=x&&t[num].r<=y)return t[num].max;
if(t[ls].r<x)return Max(rs);
if(t[rs].l>y)return Max(ls);
return max(Max(ls),Max(rs));
}
ll Min(int num){
if(t[num].l>=x&&t[num].r<=y)return t[num].min;
if(t[ls].r<x)return Min(rs);
if(t[rs].l>y)return Min(ls);
return min(Min(ls),Min(rs));
}
ll Mx(int a,int b){
x=a;y=b;
return Max(1);
}
ll Mn(int a,int b){
x=a;y=b;
return Min(1);
}
ll qy(int a,int b){
x=a;y=b;
return query(1).ans;
}
int main(){
while(T--){
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
build(1,n,1);
while(T_--){
}