After doing Ray a great favor to collect sticks for Ray, Poor Neal becomes very hungry. In return for Neal's help, Ray makes a great dinner for Neal. When it is time for dinner, Ray arranges all the dishes he makes in a single line (actually this line is
very long ... , the dishes are represented by 1, 2, 3
... ). ``You make me work hard and don't pay me! You refuse to teach me Latin Dance! Now it is time for you to serve me", Neal says to himself.
Every dish has its own value represented by an integer whose absolute value is less than 1,000,000,000. Before having dinner, Neal is wondering about the total value of the dishes he will eat. So he raises many questions about the values of dishes he would
have.
For each question Neal asks, he will first write down an interval
[a, b] (inclusive) to represent all the dishes
a, a + 1,..., b , where a and
b are positive integers, and then asks Ray which sequence of consecutive dishes in the interval has the most total value. Now Ray needs your help.
Input
The input file contains multiple test cases. For each test case, there are two integers
n and m in the first line
(n, m < 500000) .
n is the number of dishes and m is the number of questions Neal asks.
Then n numbers come in the second line, which are the values of the dishes from left to right. Next
m lines are the questions and each line contains two numbers
a , b as described above. Proceed to the end of the input file.
Output
For each test case, output m lines. Each line contains two numbers, indicating the beginning position and end position of the sequence. If there are multiple solutions, output the one with the smallest beginning position.
If there are still multiple solutions then, just output the one with the smallest end position. Please output the result as in the Sample Output.
Sample Input
3 1 1 2 3 1 1
Sample Output
Case 1:1 1
大白书P201
这题一开始想简单了，其实不简单。。
如果单纯求个 最大连续和 的话要简单许多。就不需要记录下标了，ll,rr,l,r都不需要了。
这个最大的连续和 是从 左子区间 ， 右子区间 ， 中间区间 得到。
那么每个区间除了要记录最大连续和区间的左右坐标外，还需要记录 前缀和的右端点 和 后缀和的左端点。
然后就是注意更新就行了。...
//Accepted C++ 0.172 2014-08-28 07:52:11 #include <iostream> #include<cstdio> using namespace std; #define MAXN 500000 #define LL long long struct node { LL sum,max,suf,pre; //区间和，最大连续和，最大后缀和，最大前缀和。 int l,r,ll,rr; // 最大左右端点 ， 最大前缀和右端点 ， 最大后缀和左端点 。 }tree[MAXN*3]; void push_up(int root,int left,int right) { int lc=root<<1, rc=lc+1; //得到区间和 tree[root].sum=tree[lc].sum+tree[rc].sum; //得到最大前缀和，后缀和。 if(tree[lc].sum+tree[rc].pre>tree[lc].pre) //这个地方不能 = 因为要最优解。 { tree[root].pre=tree[lc].sum+tree[rc].pre; tree[root].ll=tree[rc].ll; } else { tree[root].pre=tree[lc].pre; tree[root].ll=tree[lc].ll; } if(tree[rc].sum+tree[lc].suf >= tree[rc].suf) //这个地方则要 = { tree[root].suf=tree[rc].sum+tree[lc].suf; tree[root].rr=tree[lc].rr; } else { tree[root].suf=tree[rc].suf; tree[root].rr=tree[rc].rr; } //更新区间最大和 int t; if(tree[rc].max>tree[lc].max) t=rc; else t=lc; LL m_sum=tree[lc].suf+tree[rc].pre; if(m_sum>tree[t].max || (m_sum==tree[t].max&&tree[lc].rr<tree[t].l) || (m_sum==tree[t].max&&tree[lc].rr==tree[t].l&&tree[rc].ll<tree[t].r) ) //求最优的情况 { tree[root].max=m_sum; tree[root].l=tree[lc].rr; tree[root].r=tree[rc].ll; } else { tree[root].max=tree[t].max; tree[root].l=tree[t].l; tree[root].r=tree[t].r; } } void creat(int root,int left,int right) { if(left==right) { scanf("%lld",&tree[root].sum); tree[root].max=tree[root].pre=tree[root].suf=tree[root].sum; tree[root].l=tree[root].r=tree[root].ll=tree[root].rr=left; return ; } int mid=(left+right)>>1; int lc=root<<1,rc=lc+1; creat(lc,left,mid); creat(rc,mid+1,right); push_up(root,left,right); } node query(int root,int left,int right,int ql,int qr) // 返回的是整个区间。 { node res; if(left==ql&&right==qr) return tree[root]; int mid=(left+right)>>1; if(mid>=qr) return query(root<<1,left,mid,ql,qr); else if(mid<ql) return query(root<<1|1,mid+1,right,ql,qr); else { node t1=query(root<<1,left,mid,ql,mid); node t2=query(root<<1|1,mid+1,right,mid+1,qr); res.sum=t1.sum+t2.sum; if(t1.sum+t2.pre > t1.pre) //这个地方不能 = 因为要最优解。 { res.pre=t1.sum+t2.pre; res.ll=t2.ll; } else { res.pre=t1.pre; res.ll=t1.ll; } if(t2.sum+t1.suf >= t2.suf) //这个地方则要 = { res.suf=t2.sum+t1.suf; res.rr=t1.rr; } else { res.suf=t2.suf; res.rr=t2.rr; } node t; if(t1.max>=t2.max) t=t1; else t=t2; LL mid_sum=t1.suf+t2.pre; if(mid_sum > t.max || (mid_sum==t.max&&t1.rr<t.l) || (mid==t.max&&t1.rr==t.l&&t2.ll<t.r) ) { res.max=mid_sum; res.l=t1.rr; res.r=t2.ll; } else { res.max=t.max; res.l=t.l; res.r=t.r; } } return res; } int main() { int n,m,kase=1; while(~scanf("%d%d",&n,&m)) { creat(1,1,n); printf("Case %d:\n", kase++); int l,r; while(m--) { scanf("%d%d",&l,&r); node t=query(1,1,n,l,r); printf("%d %d\n",t.l,t.r); } } return 0; }