本文主要是介绍UVA1400 Ray, Pass me the dishes! 【线段树 区间合并】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
"Ray, Pass me the dishes!" UVA - 1400
https://vjudge.net/problem/UVA-1400
题意
给出一个长度为n的整数序列D，对m个询问做出回答，对询问(a,b)找到(x,y)使得a<=x<=y<=b且Dx+Dx+1+……+Dy最大。如有多组答案取字典序最小的一组。
题解
sum[i]记录结点i控制的区间[l,r]中区间和最大的区间
lsum[i]记录结点i控制的区间[l,r]中,从l开始往后最大连续区间和的区间右端点
rsum[i]记录结点i控制的区间[l,r]中，从r开始往前最大连续区间和的区间左端点
pre[N]存放初始数组的前缀和
C++代码
#include<iostream>
#include<utility>
#include<algorithm>using namespace std;#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1typedef long long ll;
typedef pair<int,int> interval;const int N=500500;interval sum[N<<2];//sum[i]记录结点i控制的区间[l,r]中区间和最大的区间
int lsum[N<<2];//lsum[i]记录结点i控制的区间[l,r]中,从l开始往后最大连续区间和的区间右端点
int rsum[N<<2];//rsum[i]记录结点i控制的区间[l,r]中，从r开始往前最大连续区间和的区间左端点
ll pre[N];//存放初始数组的前缀和//获取区间[l,r]的元素和
ll get_sum(int l,int r)
{return pre[r]-pre[l-1];
}ll get_sum(interval a)
{return get_sum(a.first,a.second);
}//比较两个区间的区间和，返回区间和大的区间
//如果区间和一样，返回左端点小的，左端点一样则返回右端点小的
interval better(interval a,interval b)
{ll v1=get_sum(a),v2=get_sum(b);if(v1==v2)return a<b?a:b;elsereturn v1<v2?b:a;
}//根据左右孩子结点的信息更新父亲结点的信息
void pushup(int l,int r,int rt)
{//最大和的区间sum[rt]=better(sum[rt<<1],sum[rt<<1|1]); sum[rt]=better(sum[rt],make_pair(rsum[rt<<1],lsum[rt<<1|1]));//前缀延深的最长距离（从l位置往后），记录右端点 ll v1=get_sum(l,lsum[rt<<1]);ll v2=get_sum(l,lsum[rt<<1|1]);lsum[rt]=(v2>v1?lsum[rt<<1|1]:lsum[rt<<1]);//后缀延深的最长距离（从r位置往前），记录左端点v1=get_sum(rsum[rt<<1|1],r);v2=get_sum(rsum[rt<<1],r);rsum[rt]=(v2>=v1?rsum[rt<<1]:rsum[rt<<1|1]);
}void build(int l,int r,int rt)
{if(l==r){sum[rt]=make_pair(l,r);lsum[rt]=rsum[rt]=l;return;}int m=(l+r)>>1;build(ls);build(rs);pushup(l,r,rt);
}//调用此函数的前提是l在区间[L,R]中
//求以l为起始元素，终止元素也在[L,R]中其值最大的连续字段和的区间
interval lquery(int L,int R,int l,int r,int rt)
{if(lsum[rt]<=R) return make_pair(l,lsum[rt]);int m=(l+r)>>1;if(R<=m) return lquery(L,R,ls);interval a=lquery(L,R,rs);a.first=l;return better(a,make_pair(l,lsum[rt<<1]));
}//调用此函数的前提是r在区间[L,R]中
//求以r为终止元素，起始元素也在[L,R]中其值最大的连续字段和的区间
interval rquery(int L,int R,int l,int r,int rt)
{if(rsum[rt]>=L) return make_pair(rsum[rt],r);int m=(l+r)>>1;if(m<L) return rquery(L,R,rs);interval a=rquery(L,R,ls);a.second=r;return better(a,make_pair(rsum[rt<<1|1],r));
}interval query(int L,int R,int l,int r,int rt)
{if(L<=l&&r<=R) return sum[rt];int m=(l+r)>>1;if(R<=m) return query(L,R,ls);//在左子树 if(m<L) return query(L,R,rs);//在右子树//在中间int a=rquery(L,R,ls).first;int b=lquery(L,R,rs).second;//printf("a=%d b=%d\n",a,b);interval ans=better(query(L,R,ls),query(L,R,rs));//最大子段和完全在左边和完全在右边//最大子段和在中间return better(ans,make_pair(a,b));
}int main()
{int n,m,t=1,x,L,R;while(~scanf("%d%d",&n,&m)) {pre[0]=0;//前缀和for(int i=1;i<=n;i++){scanf("%d",&x);pre[i]=pre[i-1]+x;}build(1,n,1);printf("Case %d:\n",t++);while(m--){scanf("%d%d",&L,&R);interval ans=query(L,R,1,n,1);printf("%d %d\n",ans.first,ans.second);} }return 0;
}
这篇关于UVA1400 Ray, Pass me the dishes! 【线段树 区间合并】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
