** 最大连续和(线段树+分治):** <Excerpt in index | 首页摘要>
<The rest of contents | 余下全文>
最大连续和(线段树+分治) 最大连续和 Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 61(13 users) Total Accepted: 15(9 users) Rating: Special Judge: No 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
一开始写出了这样的代码;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #include<iostream> #include<cmath> #include<stdio.h> #include<algorithm> 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<<no.sum<<endl; if(no.sum>max.sum) { max=no; // cout<<max.sum<<endl; } if(no.sum<0) { no.left=i+1; no.right=i; no.sum=0; } } return max; } int main() { int T,m,n; while(~scanf("%d",&T)) { while(T--) { int i; scanf("%d%d",&n,&m); for(i=0;i<n;i++) { scanf("%ld",&p[i]); } int x,y; while(m--) { scanf("%d%d",&x,&y); node q=check(x-1,y-1); printf("%d %d\n",q.left+1,q.right+1); } } } return 0; }
果断超时 后来想到线段树:
写出了代码,中间出了很多错误,基本都是脑残错误
原理:
每次需要比较左右子树
最大值的比较:
只需要比较三段,(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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 #include<cstdio> #include<cmath> #include<queue> #include<iostream> 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[rr].sum) { p[rt].sum=p[rr].sum; p[rt].max_l=p[rr].max_l; p[rt].max_r=p[rr].max_r; } if((p[rt].sum<p[ll].suffixSum+p[rr].prefixSum)|| (p[rt].sum==p[ll].suffixSum+p[rr].prefixSum&&p[rt].max_l>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<p[ll].all+p[rr].prefixSum) { p[rt].prefixSum=p[ll].all+p[rr].prefixSum; p[rt].pre_r=p[rr].pre_r; } if(p[rt].suffixSum<p[rr].suffixSum) { p[rt].suffixSum=p[rr].suffixSum; p[rt].suf_l=p[rr].suf_l; } } void build(int L,int R,int rt) { if(L==R) { p[rt].all=p[rt].sum=a[L]; p[rt].prefixSum=a[L]; p[rt].suffixSum=a[L]; p[rt].max_l=L; p[rt].max_r=L; p[rt].pre_r=L; p[rt].suf_l=L; return ; } int m=(L+R)>>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<l) { return query(m+1,R,l,r,rr); } 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<y.sum) { z.sum=y.sum; z.max_l=y.max_l; z.max_r=y.max_r; } if((z.sum<x.suffixSum+y.prefixSum)|| (z.sum<x.suffixSum+y.prefixSum&&z.max_l>x.suf_l)) { z.sum=x.suffixSum+y.prefixSum; z.max_l=x.suf_l; z.max_r=y.pre_r; } if(z.prefixSum<x.all+y.prefixSum) { z.prefixSum=x.all+y.prefixSum; z.pre_r=y.pre_r; } if(z.suffixSum<y.suffixSum) { z.suffixSum=y.suffixSum; z.suf_l=y.suf_l; } return z; } int main() { int T; while(~scanf("%d",&T)) { while(T--) { int n,m; scanf("%d%d",&n,&m); int i; for(i=1;i<=n;i++) { scanf("%ld",&a[i]); } build(1,n,1); while(m--) { int L,R; scanf("%d%d",&L,&R); node q=query(1,n,L,R,1); printf("%d %d\n",q.max_l,q.max_r); } } } return 0; }