COGS 775 山海经
思路:
求最大连续子段和(不能不选),只查询,无修改。要求输出该子段的起止位置。
线段树经典模型,每个节点记录权值和sum、左起最大前缀和lmax、右起最大后缀和rmax、最大子段和dat即可。
要求输出起止位置,单独维护左右端点。注意权值相同要求l、r尽量小,所以相同时选左儿子不选右儿子,维护时考虑是否加等号。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m;
struct Tree{
int l,r,lid,rid,tl,tr;
ll sum,lmax,rmax,dat;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((node[p].l+node[p].r)>>1)
}node[N<<2];
void upd(Tree &a,const Tree &b,const Tree &c){
a.sum=b.sum+c.sum;
if(b.sum+c.lmax>b.lmax){
a.lmax=b.sum+c.lmax;
a.tr=c.tr;
} else{
a.lmax=b.lmax;
a.tr=b.tr;
}
if(c.rmax>c.sum+b.rmax){
a.rmax=c.rmax;
a.tl=c.tl;
} else{
a.rmax=c.sum+b.rmax;
a.tl=b.tl;
}
if(c.dat>max(b.dat,b.rmax+c.lmax)){
a.dat=c.dat;
a.lid=c.lid;
a.rid=c.rid;
}
else{
if((b.dat>b.rmax+c.lmax)||(b.dat==b.rmax+c.lmax&&b.lid<=b.tl)){
a.dat=b.dat;
a.lid=b.lid;
a.rid=b.rid;
}
else{
a.dat=b.rmax+c.lmax;
a.lid=b.tl;
a.rid=c.tr;
}
}
}
void build(int p,int l,int r){
node[p].l=l;node[p].r=r;
if(l==r){
scanf("%lld",&node[p].sum);
node[p].dat=node[p].lmax=node[p].rmax=node[p].sum;
node[p].lid=node[p].rid=node[p].tl=node[p].tr=l;
return;
}
build(ls(p),l,mid);
build(rs(p),mid+1,r);
upd(node[p],node[ls(p)],node[rs(p)]);
}
Tree query(int p,int L,int R){
if(L<=node[p].l&&node[p].r<=R) return node[p];
Tree ans;
if(R<=mid) ans=query(ls(p),L,R);
else if(L>mid) ans=query(rs(p),L,R);
else upd(ans,query(ls(p),L,R),query(rs(p),L,R));
return ans;
}
int main(){
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1,l,r;i<=m;++i){
scanf("%d%d",&l,&r);
Tree ans=query(1,l,r);
printf("%d %d %lld\n",ans.lid,ans.rid,ans.dat);
}
return 0;
}