#include #include using namespace std; #define siz 131072 #define inf 100000000000 struct seg { long long l=-inf,m=-inf,r=-inf,sm=-inf; }tree[siz*4]; long long pref[siz]; void update(int s,int e,int l,int r,int node,long long v) { if(s>r||e>1; update(s,mid,l,r,node*2,v); update(mid+1,e,l,r,node*2+1,v); tree[node].l=max(tree[node*2].l,tree[node*2].sm+tree[node*2+1].l); tree[node].m=max(tree[node*2].r,max(tree[node*2+1].l,max(tree[node*2].r+tree[node*2+1].l,max(tree[node*2].m,tree[node*2+1].m)))); tree[node].r=max(tree[node*2+1].r,tree[node*2+1].sm+tree[node*2].r); tree[node].sm=tree[node*2].sm+tree[node*2+1].sm; } seg query(int s,int e,int l,int r,int node) { if(s>r||e>1; seg ret; seg a = query(s,mid,l,r,node*2); seg b = query(mid+1,e,l,r,node*2+1); if(a.l == -inf)ret.l=b.l; else ret.l=max(a.l,a.sm+b.l); ret.m=max(a.r,max(b.l,max(a.r+b.l,max(a.m,b.m)))); if(b.r == -inf)ret.r=a.r; else ret.r=max(b.r,b.sm+a.r); ret.sm=a.sm+b.sm; if(a.sm == -inf)ret.sm = b.sm; if(b.sm == -inf)ret.sm = a.sm; return ret; } int main() { int i,n,m; scanf("%d",&n); for(i=0;iy2)y1 = y2; if(x1>x2)x2 = x1; if(y1

코드 #1566