1.题目描述：点击打开链接
2.解题思路：本题利用线段树解决。事先构造一棵线段树，在每个线段树的结点中维护三个成员变量：max_sub,max_prefix,max_suffix。设此时线段树结点为x，左右端点分别为l,r
为了同时知道上述三个最大和的左右端点，令它们都是一个结构体segment，成员变量是l,r,val（左端点l，，右端点r，最大和val）。那么现在问题的关键是如何查找给定区间[a,b]中这个max_sub。
利用分治法的思想：假设目前为结点u,左右端点分别是L,R，中点是M。那么分三种情况：（1）起点和终点都在左子结点u*2中，那么max_sub(a,b)就是左子结点中的max_sub。
（2）起点和终点都在右子结点u*2+1中，那么max_sub(a,b)就是右子结点中的max_sub。（3）起点在左子结点中，终点在右子结点中，那么max_sub(a,b)就是左子结点的max_suffix和右子结点的max_prefix之和（注意要重载segment结构体中的’+‘）。最后取这三种情况的最大者即可（注意要重载’<‘）。
同理也可以像上述分析那样递推得到max_prefix，max_suffix，具体过程见代码注释。整个过程中建树的时间复杂度是O(N)，查询的时间复杂度是O(logN)。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 500000+10#define INF 100000000#define lson(x) ((x)<<1)//左子结点编号#define rson(x) (((x)<<1)+1)//右子结点编号typedef long long LL;struct segment{int l, r;//左右端点LL val;segment(int l = 0, int r = 0, LL val = 0){ this->set(l, r, val); }void set(int l, int r, LL val){this->l = l;this->r = r;this->val = val;}segment operator +(const segment&u)//重载加号，获得合并后的区间及区间连续和{return segment(min(l, u.l), max(r, u.r), val + u.val);}bool operator <(const segment&u)const//由于下面要取最大值，因此要重载小于号{if (val != u.val)return val < u.val;//用max函数时取以下三种情况右边的值if (l != u.l)return l>u.l;//优先让左端点最小return r>u.r;}};struct Node{int l, r;segment max_sub, max_prefix, max_suffix;}node[N*4];int n, m;LL arr[N], s[N];Node seg_push(Node a, Node b)//维护满足题意的区间{Node ret;LL suml = s[a.r] – s[a.l – 1];//a结点的连续和LL sumr = s[b.r] – s[b.l – 1];//b结点的连续和ret.l = a.l;ret.r = b.r; ret.max_sub = max(a.max_suffix + b.max_prefix, max(a.max_sub, b.max_sub));//取三种情况的最大值：(1)起点在结点a，终点在结点b中;(2)起点和终点都在结点a中;(3)起点和终点都在结点b中;ret.max_prefix = max(a.max_prefix, segment(a.l, a.r, suml) + b.max_prefix);//取两种情况的最大值：(1)终点仍在结点a中;(2)终点在结点b中ret.max_suffix = max(b.max_suffix, a.max_suffix + segment(b.l, b.r, sumr));//取两种情况的最大值：(1)起点仍在结点b中;(2)起点在结点a中return ret;}void build_segtree(int root, int l, int r){if (l == r)//叶子结点{node[root].l = node[root].r = l;node[root].max_sub.set(l, r, (LL)arr[l]);node[root].max_prefix.set(l, r, (LL)arr[l]);node[root].max_suffix.set(l, r, (LL)arr[l]);return;}int mid = (l + r) / 2;build_segtree(lson(root), l, mid);//递归建树build_segtree(rson(root), mid + 1, r);node[root] = seg_push(node[lson(root)], node[rson(root)]);//node[root]为满足题意的区间}Node query(int root, int l, int r){if (l <= node[root].l&&node[root].r <= r)//待查询区间完全包含了编号为root的线段return node[root];int mid = (node[root].l + node[root].r) / 2;if (l <= mid&&r > mid)//起点在mid左侧，终点在mid右侧return seg_push(query(lson(root), l, r), query(rson(root), l, r));else if (r <= mid)//起点和终点都在mid左侧return query(lson(root), l, r);else//起点和终点都在mid右侧return query(rson(root), l, r);}int main(){//freopen("t.txt", "r", stdin);int rnd = 1;while (~scanf("%d%d", &n, &m)){s[0] = 0;for (int i = 1; i <= n; i++){scanf("%lld", &arr[i]);s[i] = s[i – 1] + arr[i];//s[i]计算前i个的和}build_segtree(1, 1, n);//建立线段树，根结点编号为1printf("Case %d:\n", rnd++);int l, r;while (m–){scanf("%d%d", &l, &r);Node u = query(1, l, r);//从根结点开始查询线段[l,r]，返回满足题意的区间printf("%d %d\n", u.max_sub.l, u.max_sub.r);}}return 0;}
人生就像是一场旅行，遇到的既有感人的，
