目录
最大连续和(线段树+分治)

** 最大连续和(线段树+分治):** <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

一开始写出了这样的代码;

Code
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

Code
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;
}
文章作者: 爱笑的k11
文章链接: http://1315402725.github.io/posts/2d566bed/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 爱笑的k11
打赏
  • 微信
  • 支付寶

评论