"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|1

typedef 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;
	else
	  return 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;
}