"Ray, Pass me the dishes!"
题意就是线段树区间子段最大和，线段树区间合并，但是这道题还要求输出最大和的子段的左右端点。要求字典序最小，要求左右端点尽量靠左。
比如：
3 3 3 -9 3 3 3
输出的是1 3，而不是1 7
3 3 3 -9 3 3 4
输出的是1 7，而不是5 7
大体意思就是这样。
有一个坑，我没读好题，输出Case是每一组样例输出一个，而不是每查询一次就输出一次Case。。。
其他没什么了。具体代码写了注释。
代码:
1 //线段树-线段树区间合并-判断位置 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const int maxn=5e5+10; 6 #define lson l,m,rt<<1 7 #define rson m+1,r,rt<<1|1 8 9 struct Tree{ 10 ll pre,suf,sub,val;//pre最大前缀和，suf最大后缀和，sub最大子段和，val当前区间和 11 int lch,rch,lx,rx;//最大子段的左端点，最大子段的右端点，最大前缀和的右端点，最大后缀和的左端点 12 }tree[maxn<<2]; 13 14 Tree pushup(Tree l,Tree r) 15 { 16 Tree rt; 17 // rt.pre=max(l.pre,l.val+r.pre); 18 // rt.suf=max(r.suf,r.val+l.suf); 19 // rt.sub=max(max(l.sub,r.sub),l.suf+r.pre); 20 //根据上面的操作进行变形 21 if(l.pre>=l.val+r.pre){rt.pre=l.pre;rt.lx=l.lx;}//前缀和 22 else{rt.pre=l.val+r.pre;rt.lx=r.lx;} 23 if(r.val+l.suf>=r.suf){rt.suf=r.val+l.suf;rt.rx=l.rx;}//后缀和 24 else{rt.suf=r.suf;rt.rx=r.rx;} 25 if(l.sub>=r.sub&&l.sub>=(l.suf+r.pre)){rt.sub=l.sub;rt.lch=l.lch;rt.rch=l.rch;}//子段和 26 else if((l.suf+r.pre>=l.sub)&&(l.suf+r.pre>=r.sub)){rt.sub=l.suf+r.pre;rt.lch=l.rx;rt.rch=r.lx;} 27 else{rt.sub=r.sub;rt.lch=r.lch;rt.rch=r.rch;} 28 rt.val=l.val+r.val; 29 return rt; 30 } 31 32 void build(int l,int r,int rt) 33 { 34 if(l==r){ 35 scanf("%lld",&tree[rt].val); 36 tree[rt].pre=tree[rt].suf=tree[rt].sub=tree[rt].val; 37 tree[rt].lch=tree[rt].rch=tree[rt].lx=tree[rt].rx=l; 38 return ; 39 } 40 41 int m=(l+r)>>1; 42 build(lson); 43 build(rson); 44 tree[rt]=pushup(tree[rt<<1],tree[rt<<1|1]); 45 } 46 47 Tree query(int L,int R,int l,int r,int rt) 48 { 49 if(L<=l&&r<=R){ 50 return tree[rt]; 51 } 52 53 int m=(l+r)>>1; 54 Tree ret,lret,rret; 55 int flag1=0,flag2=0; 56 if(L<=m) {lret=query(L,R,lson);flag1=1;} 57 if(R> m) {rret=query(L,R,rson);flag2=1;} 58 59 if(flag1&&flag2) ret=pushup(lret,rret); 60 else if(flag1) ret=lret; 61 else if(flag2) ret=rret; 62 return ret; 63 } 64 65 int main() 66 { 67 int n,m,cas=0; 68 while(~scanf("%d%d",&n,&m)){ 69 printf("Case %d: ",++cas); 70 build(1,n,1); 71 for(int i=1;i<=m;i++){ 72 int l,r; 73 scanf("%d%d",&l,&r); 74 Tree ans=query(l,r,1,n,1); 75 printf("%d %d ",ans.lch,ans.rch); 76 } 77 } 78 }
开溜。