uvalive 3989(线段树)

题意：给出长度是n的数字序列，然后给出位置x, y，问在[x, y]这个范围内有最大和的连续子序列的范围是什么。

题解：和普通的线段树不太一样，还加入了连续子序列，求连续子序列最大和的方法有个是把序列分成三部分，最大和的起点终点可能都是左边部分，可能都是右边部分，也可能起点在左边，终点在右边，那么在用线段树时也要这样，用一个结构体表示线段树的一个结点，有左端点和右端点，也有包含在左端点和右端点内的最大和连续子序列的左右端点，还有前缀最大和和后缀最大和的位置，然后建树和查询时三者都要更新。

#include <stdio.h>
#include <string.h>
const int N = 500005;
struct Range {
	int l, r;
	Range() {}
	Range(int a, int b): l(a), r(b) {}
};
struct Node {
	int x, y, pre, suf;
	Range ran;
}node[4 * N];
int n, q, l1, r1;
long long a[N], s[N];

Range cmp(const Range& a, const Range& b) {
	long long suma = s[a.r] - s[a.l - 1];
	long long sumb = s[b.r] - s[b.l - 1];
	return (suma > sumb || (suma == sumb && a.l < b.l) || (suma == sumb && a.l == b.l && a.r < b.r)) ? a : b;
}

Node pushup(const Node& a, const Node& b) {
	Node res;
	res.x = a.x;
	res.y = b.y;
	res.ran = cmp(a.ran, b.ran);<span class="sh-comment"></span>
	res.ran = cmp(res.ran, Range(a.suf, b.pre));
	res.pre = cmp(Range(a.x, a.pre), Range(a.x, b.pre)).r;
	res.suf = cmp(Range(a.suf, b.y), Range(b.suf, b.y)).l;
	return res;
}

void build(int k, int left, int right) {
	if (left == right) {
		node[k].ran = Range(left, right);
		node[k].x = node[k].y = node[k].pre = node[k].suf = left;
		return;
	}
	int mid = (left + right) / 2;
	build(k * 2, left, mid);
	build(k * 2 + 1, mid + 1, right);
	node[k] = pushup(node[k * 2], node[k * 2 + 1]);
}

Node query(int k) {
	if (l1 <= node[k].x && r1 >= node[k].y)
		return node[k];
	int mid = (node[k].x + node[k].y) / 2;
	Node res;
	if (l1 <= mid && r1 > mid)
		res = pushup(query(k * 2), query(k * 2 + 1));
	else if (l1 <= mid)
		res = query(k * 2);
	else if (r1 > mid)
		res = query(k * 2 + 1);
	return res;
}

int main() {
	int cas = 1;
	while (scanf("%d%d", &n, &q) == 2) {
		s[0] = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &a[i]);
			s[i] = s[i - 1] + a[i];
		}
		build(1, 1, n);
		printf("Case %d:\n", cas++);
		while (q--) {
			scanf("%d%d", &l1, &r1);
			Node res = query(1);
			printf("%d %d\n", res.ran.l, res.ran.r);
		}
	}
	return 0;
}

uvalive 3989(线段树)

原文：http://blog.csdn.net/hyczms/article/details/44890995