AC得相当辛苦的一道题,似乎不难,但是需要想仔细,
开始的时候的错误思路----是受之前做过的区间最长连续子串影响http://blog.csdn.net/u011026968/article/details/38357157
区间合并的时候,我直接按照---如果(左子树的最大前缀和长度==左子树的长度 && 右子树的前缀和>0),就合并左前缀,这想法有两个错误:1、右子树的前缀和==0的时候是不是要合并区间呢?题目要求x尽量小,如果x相同y尽量小(x是ans的区间左端点,y是Ans的区间右端点),2、左子树区间3,1,-2,右子树区间9,5,-10, 那么其实根的最大前缀和还是左子树区间+右子树的部分区间,应为3,1,-2,9,5 但是按照我最初的代码,这里不进行区间合并..............
正确的合并区间的方法是,
if(右子树的前缀和+左子树的区间和<=左子树的前缀和)
根的前缀和=左子树的前缀和
else
根的前缀和=右子树的前缀和+左子树的区间和
这样也保证了x尽量小,如果x相同y尽量小(x是ans的区间左端点,y是Ans的区间右端点)
上代码:有机会和区间最长连续子串一起重写一遍
#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <cmath> #include <map> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdin) const int MAXN = 500000+500; ll sum[MAXN],a[MAXN]; struct Node{ int l,r; int ls,rs; int x,y; ll mx; }nodes[MAXN*4]; inline ll cal(int a, int b) { return sum[a]-sum[b-1]; } void pushup(int rt) { if(cal(nodes[ls(rt)].ls,nodes[rt].l) >= cal(nodes[rs(rt)].ls,nodes[rt].l)) nodes[rt].ls=nodes[ls(rt)].ls; else nodes[rt].ls=nodes[rs(rt)].ls; if(cal(nodes[rs(rt)].r,nodes[ls(rt)].rs) >= cal(nodes[rs(rt)].r,nodes[rs(rt)].rs)) nodes[rt].rs=nodes[ls(rt)].rs; else nodes[rt].rs=nodes[rs(rt)].rs; //cal mx ll vl=nodes[ls(rt)].mx; // lmx ll vr=nodes[rs(rt)].mx; //rmx ll vv=cal(nodes[rs(rt)].ls,nodes[ls(rt)].rs);//mid if(vl>=vr) { nodes[rt].x=nodes[ls(rt)].x; nodes[rt].y=nodes[ls(rt)].y; nodes[rt].mx=vl; } else { nodes[rt].x=nodes[rs(rt)].x; nodes[rt].y=nodes[rs(rt)].y; nodes[rt].mx=vr; } if(nodes[rt].mx<vv) { nodes[rt].x=nodes[ls(rt)].rs; nodes[rt].y=nodes[rs(rt)].ls; nodes[rt].mx=vv; } if(nodes[rt].mx == vv) { if(nodes[rt].x>nodes[ls(rt)].rs || (nodes[rt].x==nodes[ls(rt)].rs && nodes[rt].y>nodes[rs(rt)].ls)) { nodes[rt].x=nodes[ls(rt)].rs; nodes[rt].y=nodes[rs(rt)].ls; nodes[rt].mx=vv; } } } void build(int rt, int l, int r) { nodes[rt].l=l; nodes[rt].r=r; if(l==r) { nodes[rt].ls=nodes[rt].rs=nodes[rt].x=nodes[rt].y=l; nodes[rt].mx=a[l]; return; } int mid=(l+r)/2; build(ls(rt),l,mid); build(rs(rt),mid+1,r); pushup(rt); } Node query(int rt, int l, int r) { if(nodes[rt].l == l && nodes[rt].r == r) { return nodes[rt]; } int mid=(nodes[rt].l+nodes[rt].r)/2; if(r<=mid)return query(ls(rt),l,r); else { if(l>mid) return query(rs(rt),l,r); else { Node a,b,ans; a=query(ls(rt),l,mid); b=query(rs(rt),mid+1,r); ans.l=a.l,ans.r=b.r; ///he bing if(cal(a.ls,a.l) >= cal(b.ls, a.l)) ans.ls=a.ls; else ans.ls=b.ls; if(cal(b.r,a.rs)>=cal(b.r,b.rs)) ans.rs=a.rs; else ans.rs=b.rs; ll vl=a.mx; ll vr=b.mx; ll vv=cal(b.ls,a.rs); if(vl >=vr) { ans.mx=vl; ans.x=a.x; ans.y=a.y; } else { ans.mx=vr; ans.x=b.x; ans.y=b.y; } bool flag=0; if(ans.mx<vv) flag=1; else { if(ans.mx==vv) { if(a.rs<ans.x) flag=1; if(a.rs==ans.x && ans.y>b.ls) flag=1; } } if(flag) { ans.mx=vv; ans.x=a.rs; ans.y=b.ls; } return ans; } } } int main() { //IN("la3938.txt"); int n,m,ic=0,l,r; Node ans; while(~scanf("%d%d",&n,&m)) { sum[0]=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } build(1,1,n); printf("Case %d:\n",++ic); while(m--) { scanf("%d%d",&l,&r); ans=query(1,l,r); printf("%d %d\n",ans.x,ans.y); } } return 0; }
UVALive3938 "Ray, Pass me the dishes!" 线段树动态区间最大和,布布扣,bubuko.com
UVALive3938 "Ray, Pass me the dishes!" 线段树动态区间最大和
原文:http://blog.csdn.net/u011026968/article/details/38470905