区间最大子区间和
规定:
ls:区间靠左部分子区间最大和
rs:区间靠右部分子区间最大和
ms:区间子区间最大和
s:区间和
方程与数量关系如图所示,可以用动态规划解决
山海经题解
这题是上述方法在线段树中的应用
solution
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010;
int lid(int id){
return id<<1;
}
int rid(int id){
return id<<1|1;
}
int a[maxn],n,z,b,r,t,x,y,now,q,k,f,e,ans;
struct tree{
int lid,rid;//子区间左边界、右边界
int ms,ls,rs,s;//同上区间最大子区间和的定义
int l,r,ml,mr;//区间左边界,右边界。最大子区间和左边界,右边界
}m[maxn*4+1];
void push(int id){//对上述一堆东西的更新维护
m[id].s=m[lid(id)].s+m[rid(id)].s;
if(m[lid(id)].ls>=m[rid(id)].ls+m[lid(id)].s){m[id].ls=m[lid(id)].ls;m[id].rid=m[lid(id)].rid;}
else{m[id].ls=m[rid(id)].ls+m[lid(id)].s;m[id].rid=m[rid(id)].rid;}
if(m[rid(id)].rs>=m[rid(id)].s+m[lid(id)].rs){m[id].rs=m[rid(id)].rs;m[id].lid=m[rid(id)].lid;}
else{m[id].rs=m[rid(id)].s+m[lid(id)].rs;m[id].lid=m[lid(id)].lid;}
if(m[lid(id)].ms>=m[rid(id)].ms){m[id].ms=m[lid(id)].ms;m[id].ml=m[lid(id)].ml;m[id].mr=m[lid(id)].mr;}
else{m[id].ms=m[rid(id)].ms;m[id].ml=m[rid(id)].ml;m[id].mr=m[rid(id)].mr;}
if(m[id].ms>m[lid(id)].rs+m[rid(id)].ls) return;
if(m[id].ms<m[lid(id)].rs+m[rid(id)].ls){m[id].ms=m[lid(id)].rs+m[rid(id)].ls;m[id].ml=m[lid(id)].lid;m[id].mr=m[rid(id)].rid;return;}
if(m[id].ml<m[lid(id)].lid) return;
if(m[id].ml>m[lid(id)].lid){m[id].ml=m[lid(id)].lid;m[id].mr=m[rid(id)].rid;return;}
m[id].mr=min(m[id].mr,m[rid(id)].rid);
}
void build(int id,int l,int r){//建树
m[id].l=l;
m[id].r=r;
if(l==r){
m[id].ml=m[id].mr=m[id].lid=m[id].rid=l;
m[id].ls=m[id].rs=m[id].s=m[id].ms=a[l];
return;
}
int mid=(l+r)>>1;
build(lid(id),l,mid);
build(rid(id),mid+1,r);
push(id);
}
tree find(int id,int s,int tt){
int l=m[id].l,r=m[id].r;
if(s<=l&&r<=tt) return m[id];
int mid=(l+r)>>1;
tree x, y, w;
if(tt<=mid) return find(lid(id),s,tt);
if(s>mid) return find(rid(id),s,tt);
x=find(lid(id),s,tt);
y=find(rid(id),s,tt);
if(x.ls>=x.s+y.ls){w.ls=x.ls;w.rid=x.rid;w.l=x.l;}
else{w.ls=x.s+y.ls;w.rid=y.rid;w.l=x.l;}
if(y.rs>=x.rs+y.s){w.rs=y.rs;w.lid=y.lid;w.r=y.r;}
else{w.rs=x.rs+y.s;w.lid=x.lid;w.r=y.r;}
if(x.ms>=y.ms){w.ms=x.ms;w.ml=x.ml;w.mr=x.mr;}
else{w.ms=y.ms;w.ml=y.ml;w.mr=y.mr;}
if(w.ms>x.rs+y.ls)return w;
if(w.ms<x.rs+y.ls){w.ms=x.rs+y.ls;w.ml=x.lid;w.mr=y.rid;return w;}
if(w.ml<x.lid) return w;
if(w.ml>x.lid){w.ml=x.lid;w.mr=y.rid;return w;}
w.mr=min(w.mr,y.rid);
return w;
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
// modify (1,i,a[i]);
}
if(n!=0) build(1,1,n);
for(int i=1;i<=q;i++){
scanf("%d%d",&f,&e);
tree mm=find(1,f,e);
printf("%d %d %d\n",mm.ml,mm.mr,mm.ms);
}
return 0;
}
标签:lid,山海经,rs,题解,ls,ms,区间,rid,id
From: https://www.cnblogs.com/dfxjlsx/p/18019069