LA3938-Ray, Pass me the dishes!（线段树区间合并+动态区间最大和位置）

• 我们先定义三个变量
  1. int prefix ：表示该区间内最大前缀的尾标
  2. int suffix：表示该区间内最大后缀的首标
  3. pari<int,int>medium：表示该区间最大连续和的首标和尾标
• 然后我们思考如何进行区间合并
  • prefix：取 max（左子区间的最大前缀，左子区间和+右子区间最大前缀），注意，这里不是当左子区间的前缀等于左子区间长度时才加上右子区间前缀，直观来说，只要右子区间前缀足够抵消加上左子区间非最大前缀部分，我们都是应该加上右子区间的
  • suffix：取 max（右子区间的最大后缀，右子区间和+左子区间最大后缀），注意点同上
  • medium：取 max（左子区间最大连续和，右子区间最大连续和，左子区间最大后缀+右子区间最大前缀）
•  最后我们思考如何查询，或者说何时需要进行区间合并
  1. 需要查询的区间的l在当前区间的左子区间，r在当前区间的右子区间时，需要向下查询左、右子区间，并合并
  2. l、r都在左子区间，向下查询左子区间
  3. l、r都在右子区间内，向下查询右子区间

1. 如何用合适的变量表示所需区间的权值
2. 如何进行区间合并
3. 何时进行区间合并

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int maxn=500000+10;
typedef long long ll;
typedef pair<int,int> par;
ll a[maxn];
int n,q,temp,l,r;
ll sum[maxn];//前缀和,要求一段区间的值就是sum[r]-sum[l-1]

struct node {
	int l,r,prefix,suffix;//左右节点，最大前缀和终点，最大后缀和起点
	par medium;//结果
} tree[maxn<<2];
ll cal(par x) {
	return sum[x.second]-sum[x.first-1];//求区间和
}
//比较两个区间和大小
par cmp(par x,par y) {
	ll a=cal(x);
	ll b=cal(y);
	if(a!=b) return a>b?x:y;
	return x<y?x:y;
}
//合并
node com(node x,node y) {
	node res;
	res.l=x.l;
	res.r=y.r;
	res.prefix=cmp(par(x.l,x.prefix),par(x.l,y.prefix)).second;//新节点的最大前缀和终点
	res.suffix=cmp(par(y.suffix,y.r),par(x.suffix,y.r)).first;//新节点的最大后缀和起点
	//答案的区间只会有三种情况，要么左边，要么右边，要么中间
	res.medium=cmp(par(x.suffix,y.prefix),cmp(x.medium,y.medium));
	return res;
}
void build(int l,int r,int root) {
	if(l==r) {
		//根节点
		tree[root].l=tree[root].r=tree[root].prefix=tree[root].suffix=l;
		tree[root].medium=par(l,l);
		return;
	}
	int m=(l+r)/2;
	build(l,m,root*2);//左节点
	build(m+1,r,root*2+1);//右节点
	tree[root]=com(tree[root*2],tree[root*2+1]);//合并
}
node query(int l,int r,int root) {
	if(tree[root].l>=l&&tree[root].r<=r)return tree[root];
	int m=(tree[root].l+tree[root].r)/2;
	node res;
	if(l<=m&&r>m)res=com(query(l,r,root*2),query(l,r,root*2+1));//查询区间包含左右合集
	else if (l<=m)  res=query(l,r,root*2); //l<=m且r<=m，说明只在左边
	else res=query(l,r,root*2+1);   //l>m且r>m说明只在右边
	return res;
}
int main() {
	int index=1;
	while(scanf("%d%d",&n,&q)!=EOF) {
		memset(sum,0,sizeof(sum));
		for(int i=1; i<=n; i++) {
			scanf("%lld",&a[i]);
			sum[i]=a[i]+sum[i-1];
		}
		build(1,n,1);
		printf("Case %d:\n",index++);
		for(int i=1; i<=q; ++i) {
			scanf("%d%d",&l,&r);
			par ans=query(l,r,1).medium;
			printf("%d %d\n",ans.first,ans.second);
		}
	}
	return 0;
}