盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

LA 3938 动态最大连续和(线段树)

题目

源地址:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=22&problem=1939&mosmsg=Submission+received+with+ID+1584539

题意

给定一个序列,长度为n。有m个操作,每次操作给定(a,b)。求区间[a,b]之间的一段区间[l,r],使得a ≤ l ≤ r ≤ b。且区间[l,r]为最大子段和。当有多组答案时,使l最小,l相同时,r最小。
数据范围:1 ≤ n,m ≤ 500000,序列元素的绝对值 ≤ 1e9

思路

采用线段树来维护动态最大连续和。每个区间维护最大子段和sub[],最大前缀和pre[],最大后缀和[]。在建立线段树的时候,进行维护。当左右两个区间l,r进行合并时,维护的方式是:

  • prefix 最大前缀和为max(pre[l], sum[l] + pre[r])
  • suffix 最大后缀和为max(suf[r], sum[r] + suf[l])
  • sub 最大子段和为max(max(sub[l], suf[l] + pre[r]), sub[r])
    在维护的过程中,还要记录相应的坐标信息
    查询相似

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn = 500100;
ll sub[maxn << 2], pre[maxn << 2], suf[maxn << 2]; //记录每段的最大子段和,最大前缀和,最大后缀和
ll sum[maxn << 2]; //记录每段的和
ll st[maxn << 2], ed[maxn << 2]; //记录最大子段和的起点、终点
ll pst[maxn << 2], ped[maxn << 2]; //记录最大前缀和的起点、终点
ll sst[maxn << 2], sed[maxn << 2]; //记录最大后缀和的起点、终点
int n, m;
void pushup(int rt) {
int l = rt << 1, r = rt << 1 | 1;
sum[rt] = sum[l] + sum[r];
//prefix
ll maxt = pre[l];
ll ss = pst[l], ee = ped[l];
if (pre[l] < sum[l] + pre[r])
maxt = sum[l] + pre[r], ss = pst[l], ee = ped[r];
pre[rt] = maxt, pst[rt] = ss, ped[rt] = ee;
//suffix
maxt = suf[r], ss = sst[r], ee = sed[r];
if (suf[r] <= sum[r] + suf[l])
maxt = sum[r] + suf[l], ss = sst[l], ee = sed[r];
suf[rt] = maxt, sst[rt] = ss, sed[rt] = ee;
//sub
maxt = sub[l], ss = st[l], ee = ed[l];
if (maxt < suf[l] + pre[r]) maxt = suf[l] + pre[r], ss = sst[l], ee = ped[r];
if (maxt < sub[r]) maxt = sub[r], ss = st[r], ee = ed[r];
sub[rt] = maxt, st[rt] = ss, ed[rt] = ee;
}
void build(int l, int r, int rt) {
if (l == r) {
scanf("%lld", sum + rt);
sub[rt] = pre[rt] = suf[rt] = sum[rt];
st[rt] = ed[rt] = pst[rt] = ped[rt] = sst[rt] = sed[rt] = l;
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}
struct node {
ll sum, l, m, r; //sum表示该段和,l,m,r分别表示最大前缀和、最大子段和、最大后缀和
int ls, le, ms, me, rs, re; //分别表示l,m,r的起点、终点
};
node query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
node tp;
tp.l = pre[rt], tp.m = sub[rt], tp.r = suf[rt];
tp.ls = pst[rt], tp.le = ped[rt];
tp.ms = st[rt], tp.me = ed[rt];
tp.rs = sst[rt], tp.re = sed[rt];
tp.sum = sum[rt];
return tp;
}
node tp, tp1, tp2;
int m = (l + r) >> 1, sl = 0, sr = 0;
if (L <= m) {
tp1 = query(L, R, lson);
sl = 1;
}
if (R > m) {
tp2 = query(L, R, rson);
sr = 1;
}
if (sl && !sr) return tp1;
if (!sl && sr) return tp2;
//prefix
tp.l = tp1.l, tp.ls = tp1.ls, tp.le = tp1.le;
if (tp.l < tp1.sum + tp2.l)
tp.l = tp1.sum + tp2.l, tp.le = tp2.le;
//suffix
tp.r = tp2.r, tp.rs = tp2.rs, tp.re = tp2.re;
if (tp.r <= tp2.sum + tp1.r)
tp.r = tp2.sum + tp1.r, tp.rs = tp1.rs;
//sub
tp.m = tp1.m, tp.ms = tp1.ms, tp.me = tp1.me;
if (tp.m < tp1.r + tp2.l)
tp.m = tp1.r + tp2.l, tp.ms = tp1.rs, tp.me = tp2.le;
if (tp.m < tp2.m)
tp.m = tp2.m, tp.ms = tp2.ms, tp.me = tp2.me;
tp.sum = tp1.sum + tp2.sum;
return tp;
}
int main () {
int cas = 1;
while(~scanf("%d%d", &n, &m)) {
build(1, n, 1);
printf("Case %d:\n", cas++);
int a, b;
while(m--) {
scanf("%d%d", &a, &b);
node ans = query(a, b, 1, n, 1);
printf("%d %d\n", ans.ms, ans.me);
}
}
return 0;
}

更新日志

  • 2014-10-27 已AC
  • 3938 “Ray, Pass me the dishes!” Accepted C++11 0.219 2014-10-26 16:33:27