网上似乎这道题的题解很少？写一个吧
我跟这道题的渊源追溯到了上个学期刚刚学线段树的那一天。。。
当时线段树专题前边的题都是一些板子就不一会就水过了，然后就看到了最后一题的它：山海经
那一个上午，我竭尽全力，却毫无收获。
后来我下午继续肛还是肛不动，但是mikufun大神，在刚学线段树的阶段，把这道我现在都要写30min的难题给A了！
他当时的NB代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 struct tree{ 5 int l,r,da,dam,dal,dar; 6 int lme,lmr,le,lr; 7 }t[1000000]; 8 void build(int l1,int r1,int k){ 9 t[k].l=l1,t[k].r=r1; 10 if(l1==r1){ 11 scanf("%d",&t[k].da); 12 t[k].dal=t[k].dam=t[k].dar=t[k].da; 13 t[k].le=t[k].lme=t[k].lmr=t[k].lr=l1; 14 return; 15 } 16 int mid=(l1+r1)/2; 17 build(l1,mid,k*2); 18 build(mid+1,r1,k*2+1); 19 t[k].da=t[k*2].da+t[k*2+1].da; 20 if(t[k*2].dal>=t[k*2].da+t[k*2+1].dal){ 21 t[k].dal=t[k*2].dal; 22 t[k].le=t[k*2].le; 23 } 24 else{ 25 t[k].dal=t[k*2].da+t[k*2+1].dal; 26 t[k].le=t[k*2+1].le; 27 } 28 if(t[k*2+1].dar>t[k*2+1].da+t[k*2].dar){ 29 t[k].dar=t[k*2+1].dar; 30 t[k].lr=t[k*2+1].lr; 31 } 32 else{ 33 t[k].dar=t[k*2+1].da+t[k*2].dar; 34 t[k].lr=t[k*2].lr; 35 } 36 if(max(t[k*2].dam,max(t[k*2+1].dam,t[k*2].dar+t[k*2+1].dal))==t[k*2].dam){ 37 t[k].dam=t[k*2].dam; 38 t[k].lme=t[k*2].lme;t[k].lmr=t[k*2].lmr; 39 } 40 else if(max(t[k*2].dam,max(t[k*2+1].dam,t[k*2].dar+t[k*2+1].dal))==t[k*2+1].dam){ 41 t[k].dam=t[k*2+1].dam; 42 t[k].lme=t[k*2+1].lme;t[k].lmr=t[k*2+1].lmr; 43 } 44 else if(max(t[k*2].dam,max(t[k*2+1].dam,t[k*2].dar+t[k*2+1].dal))==t[k*2].dar+t[k*2+1].dal){ 45 t[k].dam=t[k*2].dar+t[k*2+1].dal; 46 t[k].lme=t[k*2].lr;t[k].lmr=t[k*2+1].le; 47 } 48 } 49 inline int sea_qu(int l1,int r1,int k,int x,int &ll,int &rr){ 50 if(l1<=t[k].l&&t[k].r<=r1){ 51 if(!x){ 52 ll=t[k].lme;rr=t[k].lmr; 53 return t[k].dam; 54 } 55 if(x==1){ 56 ll=t[k].lr;rr=t[k].r; 57 return t[k].dar; 58 } 59 if(x==2){ 60 ll=t[k].l;rr=t[k].le; 61 return t[k].dal; 62 } 63 } 64 int mid=(t[k].l+t[k].r)/2,ans,a1,a2,a3,a4,a5,a6; 65 int a,b,c,d,e,g,h,z; 66 if(x==1){ 67 a1=sea_qu(l1,r1,k*2+1,1,a,b); 68 ll=a;rr=t[k].r; 69 if(l1<=mid){ 70 a5=sea_qu(l1,r1,k*2,1,b,c)+t[k*2+1].da; 71 if(a5>a1){ 72 ll=b,rr=t[k].r; 73 return a5; 74 } 75 } 76 return a1; 77 } 78 if(x==2){ 79 a2=sea_qu(l1,r1,k*2,2,z,c); 80 rr=c;ll=t[k].l; 81 if(r1>mid){ 82 a6=sea_qu(l1,r1,k*2+1,2,b,z)+t[k*2].da; 83 if(a6>a2){ 84 ll=t[k].l,rr=z; 85 return a6; 86 } 87 } 88 return a2; 89 } 90 if(!x){ 91 if(r1<=mid){ 92 ans=sea_qu(l1,r1,k*2,0,ll,rr); 93 return ans; 94 } 95 if(l1>mid){ 96 ans=sea_qu(l1,r1,k*2+1,0,ll,rr); 97 return ans; 98 } 99 a1=sea_qu(l1,r1,k*2,1,a,b); 100 a2=sea_qu(l1,r1,k*2+1,2,b,c); 101 a3=sea_qu(l1,r1,k*2,0,h,d); 102 a4=sea_qu(l1,r1,k*2+1,0,e,g); 103 if(max(a1+a2,max(a3,a4))==a3){ 104 ll=h,rr=d; 105 return a3; 106 } 107 if(max(a1+a2,max(a3,a4))==a1+a2){ 108 ll=a; 109 rr=c; 110 return a1+a2; 111 } 112 if(max(a1+a2,max(a3,a4))==a4){ 113 ll=e,rr=g; 114 return a4; 115 } 116 } 117 } 118 int main(){ 119 int n,m,x,y,ll,rr; 120 scanf("%d%d",&n,&m); 121 build(1,n,1); 122 for(int i=1;i<=m;i++){ 123 scanf("%d%d",&x,&y); 124 int ans=sea_qu(x,y,1,0,ll,rr); 125 cout<<ll<<" "<<rr<<" "<<ans<<endl; 126 } 127 return 0; 128 }
这可是在当时，也就是没有题能打50行+的时候啊。
我当时看到有人A了都惊呆了。
我就去问mikufun，然后他说：“自己再想一想。”
我后来就一直想A掉这道题，可总有一些理由阻挡我蹒跚前进的脚步。
但现在我终于A了，很轻松释然。
我记得当时老吕看只有mikufunA了这道题，鼓励我们：“没事，只要知识没有丢，这些题你们以后看都很简单的。”
可是我当时想：“这么难的题，我恐怕一辈子都做不对了。”没想到啊，才几个月，变化已经这么大了。
OI改变你我。
题解：线段树维护左端点开始的最大值，右端点开始的最大值，区间最大值，以及它们的端点。
在子树合并到父亲时，父亲左端点开始的最大值可以由左儿子左端点开始的最大值，左儿子全部值+右左端点开始的最大值来更新。
同理于父亲右端点开始的最大值，区间最大值。但区间最大值还能够由左儿子右端点的最大值+右儿子左端点的最大值来更新。
总体上细节挺多的，注意好它字典序问题。其实就是几个顺序的调整罢了。
在merge合并时，我为了之后的查询更加方便，选择了用结构体进行合并，因为在find查找时由于[a,b]区间会被分成log个区间，因此等效于在子树合并到父亲。
1 #include<bits/stdc++.h> 2 #define N 100005 3 #define Inf 0x7f7f7f7f 4 #define lch k<<1 5 #define rch k<<1|1 6 inline int read(){ 7 int x=0,f=1;char ch=getchar(); 8 while(!isdigit(ch))f=(ch=='-'?-1:1),ch=getchar(); 9 while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); 10 return x*f; 11 } 12 struct node{int l,r,mx,lmx,lp,rmx,rp,smx,slp,srp;}tr[N<<2]; 13 int n,m; 14 node merge(const node &t1,const node &t2){ 15 node ret;ret.lmx=ret.rmx=ret.smx=-Inf; 16 ret.l=t1.l,ret.r=t2.r;ret.mx=t1.mx+t2.mx; 17 ret.lmx=t1.lmx,ret.lp=t1.lp; 18 ret.rmx=t2.rmx,ret.rp=t2.rp; 19 if(t1.smx>=t2.smx) ret.smx=t1.smx,ret.slp=t1.slp,ret.srp=t1.srp; 20 if(t1.rmx+t2.lmx>ret.smx) ret.smx=t1.rmx+t2.lmx,ret.slp=t1.rp,ret.srp=t2.lp; 21 if(t1.rmx+t2.lmx==ret.smx&&( (t1.rp<ret.slp) || (t1.rp==ret.slp && t2.lp<ret.srp) )) ret.smx=t1.rmx+t2.lmx,ret.slp=t1.rp,ret.srp=t2.lp; 22 if(t2.smx>ret.smx) ret.smx=t2.smx,ret.slp=t2.slp,ret.srp=t2.srp; 23 if(t1.mx+t2.lmx>ret.lmx) ret.lmx=t1.mx+t2.lmx,ret.lp=t2.lp; 24 if(t2.mx+t1.rmx>ret.rmx) ret.rmx=t2.mx+t1.rmx,ret.rp=t1.rp; 25 if(ret.smx<=ret.lmx) ret.slp=ret.l,ret.srp=ret.lp; 26 if(ret.smx<ret.rmx) ret.slp=ret.rp,ret.srp=ret.r; 27 return ret; 28 } 29 void build(int k,int l,int r){ 30 tr[k].l=l,tr[k].r=r; 31 if(l==r){tr[k].mx=tr[k].lmx=tr[k].rmx=tr[k].smx=read();tr[k].lp=tr[k].rp=tr[k].slp=tr[k].srp=l;return;} 32 const int mid=(l+r)>>1; 33 build(lch,l,mid),build(rch,mid+1,r); 34 tr[k]=merge(tr[lch],tr[rch]); 35 } 36 node find(int k,int l,int r){ 37 if(tr[k].l>=l&&tr[k].r<=r) return tr[k]; 38 node ret; 39 if(l<=tr[lch].r&&r>=tr[rch].l) ret=merge(find(lch,l,r),find(rch,l,r)); 40 else if(r<=tr[lch].r) ret=find(lch,l,r); 41 else if(l>=tr[rch].l) ret=find(rch,l,r); 42 return ret; 43 } 44 int main(){ 45 n=read(),m=read(); 46 build(1,1,n); 47 int a,b; 48 for(int i=1;i<=m;++i){ 49 a=read(),b=read(); 50 node ret=find(1,a,b); 51 printf("%d %d %d ",ret.slp,ret.srp,ret.smx); 52 } 53 }