最大连续和 | ||||||
| ||||||
Description | ||||||
给出一个长度为n的整数序列D,你的任务是对m个询问做出回答。对于询问(a,b),需要找到 两个下标x和y,使得a<=x<=y<=b,并且Dx+Dx+1+....+Dy尽量大。如果有多组满足条件的x和y,x 应尽量小。如果还有多解y也应尽量小。 | ||||||
Input | ||||||
第一行是一个整数T,代表测试数据组数。 对于每组测试数据,第一行为一个整数(1<=n,m<=500000),即整数序列的查询的个数。 第二行包含n个整数,依次为D1,D2,...Dn的值。这些整数绝对值不超过10^9。以下m行 每行为一个查询,包含两个整数a和b。 | ||||||
Output | ||||||
对于每组数据,对于每个查询输出一行包含两个整数x和y。 | ||||||
Sample Input | ||||||
1 8 3 -2 3 4 -6 6 10 -7 100 1 8 3 5 6 8 | ||||||
Sample Output | ||||||
2 8 5 5 6 8 | ||||||
Author | ||||||
陈禹@HRBUST |
一开始写出了这样的代码;
#include#include #include #include using namespace std;typedef long LONG;LONG p[500000];struct node{ LONG sum; int left,right;};node check(int i1,int i2){ node no,max; no.sum=0; no.left=i1; no.right=i1-1; //max.sum=-9223372036854775808; max.sum=-5000000; max.left=i1; max.right=i1; int i; for(i=i1;i<=i2;i++) { no.sum+=p[i]; no.right++; // cout< < max.sum) { max=no; // cout< <
果断超时
后来想到线段树:写出了代码,中间出了很多错误,基本都是脑残错误
原理:
每次需要比较左右子树
最大值的比较:
只需要比较三段,(1)max_left,(2)max_right(3)max_left_suffix+max_right_prefix
以最左边第一个元素为起点的最大值,为什么要更新他,为了使其父亲线段获得最大值
(1)比较 max_left_prefix与left_all+max_right_prefix
以最右边最后一个元素开始往左的最大值
(1)比较max_right_suffix与right_all+max_left_suffix
#include#include #include #include using namespace std;const int SIZE=500005;typedef long LL;struct node{ LL sum,all; int pre_r,suf_l; int max_l,max_r; LL prefixSum,suffixSum;} p[SIZE<<2];LL a[SIZE];void pushup(int L,int R,int rt){ int ll=rt<<1; int rr=rt<<1|1; p[rt].all=p[ll].all+p[rr].all; p[rt].prefixSum=p[ll].prefixSum; p[rt].pre_r=p[ll].pre_r; p[rt].suffixSum=p[rr].all+p[ll].suffixSum; p[rt].suf_l=p[ll].suf_l; p[rt].sum=p[ll].sum; p[rt].max_l=p[ll].max_l; p[rt].max_r=p[ll].max_r; if(p[rt].sum p[ll].suf_l)) { p[rt].sum=p[ll].suffixSum+p[rr].prefixSum; p[rt].max_l=p[ll].suf_l; p[rt].max_r=p[rr].pre_r; } if(p[rt].prefixSum >1; int ll=rt<<1; int rr=rt<<1|1; build(L,m,ll); build(m+1,R,rr); pushup(L,R,rt);}node query(int L,int R,int l,int r,int rt){ if(L==l&&R==r) { return p[rt]; } /* if(L==R) 这一段时不可取的,这回大大投稿时间复杂度 { return p[rt]; }*/ int m=(L+R)>>1; int ll=rt<<1; int rr=rt<<1|1; if(m =r) { return query(L,m,l,r,ll); } node x=query(L,m,l,m,ll); node y=query(m+1,R,m+1,r,rr); node z; z.all=x.all+y.all; z.sum=x.sum; z.max_l=x.max_l; z.max_r=x.max_r; z.prefixSum=x.prefixSum; z.pre_r=x.pre_r; z.suffixSum=x.suffixSum+y.all; z.suf_l=x.suf_l; if(z.sum x.suf_l)) { z.sum=x.suffixSum+y.prefixSum; z.max_l=x.suf_l; z.max_r=y.pre_r; } if(z.prefixSum