uva 1400 "Ray, Pass me the dishes!"

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

题意:给出一个区间从1到n标号,每个单元有一个值,可正可负。每个询问给出一段区间,问这段区间里面的最大子序列和所在的位置,越靠左越好,即序列和相同时,优先选择左端点靠左的区间,如果左端点也相同,优先选择右端点靠左的区间。只需要序列和的位置不需要具体的值

回顾怎么求最大子序列和,最优的方法是动态规划,O(n)出答案,但是这题每次询问的区间不同,而且询问次数很多,如果每次都做一次动态规划,恐怕不行。求最大子序列和另一个高效的方法是分治法,复杂度O(nlogn).这题就是利用分治法来求的。为什么可以这样求,因为先做一次预处理的话,整个区间的一些信息就可以出来,虽然多次询问,但是每次都可以利用预处理出来的信息而不必重新计算,相当于每个查询都是O(logn)出答案。而线段树有区间又有分治,二分之类的作用,所以用线段树辅助

线段树节点应该记录的信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct SegTree{
int l,r; //该节点表示的区间
LL pre; int posp; //维护该区间的最大前缀和,并记录最大前缀和位置的右端点posp
LL suf; int poss; //维护该区间的最大后缀和,并记录最大后缀和位置的左端点poss
LL Max; int posl,posr; //该区间内最大子序列和,并记录位置即左右端点posl,posr
LL sum; //该区间的总和
SegTree(){}
SegTree(int _l,int _r){ //构造函数
l = _l; r = _r;
pre = suf = sum = Max = -INF;
posp = poss = posl = posr = r;
}
int mid(){ //求该区间的终点
return (l+r) >> 1;
}
}t[MAX<<2];

回忆分治法求最大子序列和步骤

  1. 该区间的最大子序列和等于左半区间的最大子序列和
  2. 该区间的最大子序列和等于右半区间的最大子序列和
  3. 该区间的最大子序列和等于左半,右半区间相接处部分相加的和,也就是左半区间的最大后缀和 + 右区间的最大前缀和
  4. 上面三者的最大者

为了查询时可以利用这些信息,我们在构建线段树的时候就要为何好每个节点的信息。注意这题,节点的信息一旦计算好了以后都不会改变,查询只是利用了节点的信息而不做出任何的修改

  1. 区间总和 = 左孩子区间总和 + 右孩子区间总和
  2. 区间最大前缀和 = max{ 左孩子区间最大前缀和 , 左孩子区间总和+右孩子区间最大前缀和 }
  3. 区间最大后缀和 = max{ 右孩子区间最大后缀和 , 左孩子最大后缀和+右孩子区间总和}
  4. 区间最大子序列和 = max{ 左孩子区间最大子序列和,右孩子区间最大子序列和,左孩子最大后缀和+右孩子最大前缀和 }

建树的过程中,递归返回后,通过PushUp函数,利用左右孩子的信息去更新当前区间的信息即可

对于每个查询操作,在线段树上进行分割,分割出的小区间在合并过程通过updata函数传递上去

这题写了很久,收获良多,算是非常经典的题目,写完后觉得其实也不难的,但是写的过程中,没有想清楚。

这题和一般的线段树不同,这题在build tree过程中,做了很多工作,并且在以后的过程中都不修改,只是利用保存好的信息,和一般的线段树要修改区间信息大有不同

注意一点:上面列出的更新的,如果是严格的 > 就必定更新,如果是出现 == 的情况则要讨论,因为这题需要区间最靠左。另外并不是所有情况都要讨论 == ,因为可以知道有些情况下 == 是不必要更新的,因为必定使区间靠右了。这些情况下写之前应该想清楚。

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
162
163
164
165
166
167
168
169
170
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 500010
#define INF 0x3f3f3f3f
#define LL long long
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n,q;
struct SegTree{
int l,r;
LL pre; int posp;
LL suf; int poss;
LL Max; int posl,posr;
LL sum;
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r;
pre = suf = sum = Max = -INF;
posp = poss = posl = posr = r;
}
int mid(){
return (l+r) >> 1;
}
}t[MAX<<2];

void PushUp(int rt){
t[rt].sum = t[lson(rt)].sum + t[rson(rt)].sum;
/*********************** 更新pre前缀和 ****************************/
if(t[lson(rt)].pre > t[rt].pre){
t[rt].pre = t[lson(rt)].pre;
t[rt].posp = t[lson(rt)].posp;
}
if(t[lson(rt)].sum + t[rson(rt)].pre > t[rt].pre){
t[rt].pre = t[lson(rt)].sum + t[rson(rt)].pre;
t[rt].posp = t[rson(rt)].posp;
}
/***********************更新后缀和suf ***********************/
if(t[rson(rt)].suf > t[rt].suf){
t[rt].suf = t[rson(rt)].suf;
t[rt].poss = t[rson(rt)].poss;
}
if(t[lson(rt)].suf + t[rson(rt)].sum >= t[rt].suf){ // >=
t[rt].suf = t[lson(rt)].suf + t[rson(rt)].sum;
t[rt].poss = t[lson(rt)].poss;
}
/*********************** 更新Max ************************/
if(t[lson(rt)].Max > t[rt].Max){
t[rt].Max = t[lson(rt)].Max;
t[rt].posl = t[lson(rt)].posl;
t[rt].posr = t[lson(rt)].posr;
}
if(t[rson(rt)].Max > t[rt].Max){
t[rt].Max = t[rson(rt)].Max;
t[rt].posl = t[rson(rt)].posl;
t[rt].posr = t[rson(rt)].posr;
}
if(t[lson(rt)].suf + t[rson(rt)].pre > t[rt].Max ||
(t[lson(rt)].suf + t[rson(rt)].pre == t[rt].Max &&
(t[lson(rt)].poss < t[rt].posl || t[rson(rt)].posp < t[rt].posr))){
t[rt].Max = t[lson(rt)].suf + t[rson(rt)].pre;
t[rt].posl = t[lson(rt)].poss;
t[rt].posr = t[rson(rt)].posp;
}
}

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b){
LL val;
scanf("%lld",&val);
t[rt].pre = t[rt].suf = t[rt].sum = t[rt].Max = val;
t[rt].posp = t[rt].poss = t[rt].posl = t[rt].posr = a;
return ;
}
int mid = t[rt].mid();
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
PushUp(rt);
}

SegTree updata(SegTree ll,SegTree rr){
SegTree res = SegTree(ll.l , rr.r);
res.sum = ll.sum + rr.sum;
/*************** 更新pre ****************/
if(ll.pre > res.pre){
res.pre = ll.pre;
res.posp = ll.posp;
}
if(ll.sum + rr.pre > res.pre){
res.pre = ll.sum + rr.pre;
res.posp = rr.posp;
}
/************** 更新suf ***************/
if(rr.suf > res.suf){
res.suf = rr.suf;
res.poss = rr.poss;
}
if(ll.suf + rr.sum >= res.suf){
res.suf = ll.suf + rr.sum;
res.poss = ll.poss;
}
/**************** 更新Max *****************/
if(ll.Max > res.Max){
res.Max = ll.Max;
res.posl = ll.posl;
res.posr = ll.posr;
}
if(rr.Max > res.Max){
res.Max = rr.Max;
res.posl = rr.posl;
res.posr = rr.posr;
}
if(ll.suf + rr.pre > res.Max ||
(ll.suf + rr.pre == res.Max &&
(ll.poss < res.posl || rr.posp < res.posr))){
res.Max = ll.suf + rr.pre;
res.posl = ll.poss;
res.posr = rr.posp;
}

return res;
}

SegTree query(int rt,int a,int b){
if(t[rt].l == a && t[rt].r == b)
return t[rt];
int mid = t[rt].mid();
if(b <= mid)
return query(lson(rt),a,b);
else if(a > mid)
return query(rson(rt),a,b);
else{
SegTree ll = query(lson(rt),a,mid);
SegTree rr = query(rson(rt),mid+1,b);
SegTree res = updata(ll,rr);
return res;
}
}

int main(){
int cas = 0;
while(scanf("%d%d",&n,&q)!=EOF){
build(1,1,n);
//output(1);
printf("Case %d:\n",++cas);
while(q--){
int x,y;
scanf("%d%d",&x,&y);
SegTree res = query(1,x,y);
//printf("%lld %d %d\n",res.Max,res.posl,res.posr);
printf("%d %d\n",res.posl,res.posr);
}
}
return 0;
}
/*
void output(int rt){
printf("[%d , %d] ",t[rt].l,t[rt].r);
printf(" 前缀=%lld %d |",t[rt].pre,t[rt].posp);
printf(" 后缀=%lld %d |",t[rt].suf,t[rt].poss);
printf(" 最大值=%lld [%d,%d]",t[rt].Max,t[rt].posl,t[rt].posr);
printf(" 总和=%lld\n",t[rt].sum);
if(t[rt].l == t[rt].r) return ;
output(lson(rt));
output(rson(rt));
}
*/