题解 UVA1400 【"Ray, Pass me the dishes!"】
UVA1400 "Ray, Pass me the dishes!" uva1400 的合并真恶心。
题意：给出一个长度为n的整数序列D，你的任务是对m个询问做出回答。
对于询问（a,b），需要找到两个下标x和y，
使得a<=x<=y<=b，并且Dx+Dx+1+....+Dy尽量大。
如果有多组满足条件的x和y，x尽量小。
如果还有多个解，y应该尽量小。
思路：这题难在合并，单点修改很容易。我们可以分类讨论，一个区间的最大子段和会从3部分更新过来：
1.左子树的最大子段和。2.右子树的最大子段和。3.跨越左右子树的最大子段和。 我们需要一个结构体：
struct Tree{
LL pre,suf,sub,val,lch,rch,ll,rr;
// 前缀 后缀 最大字段和 区间和 字段和左端点和右端点 前缀和右端点 后缀和左端点
}tree[N<<2];
``
pre为当前区间的最大前缀和，suf为当前区间的最大后缀和，sub为当前区间的最大子段和，val为当前区间的和。
可以发现，第三种情况为 左子树的最大后缀和+右子树的最大前缀和。
为什么要多记录这4个东西？它要求的不是最大子段和，而是最大子段和的左右端点，我们考虑合并的时候需要用到最大子段和，前缀和，后缀和，所以我们需要记录这些。
合并的时候需要分类讨论：****
1.在保证最大子段和的前提下，x尽量小的情况下，y也尽量小。
上一道题怎么合并的？取了3个max，总共有7种情况，分类讨论就好了，
完整代码：
```c
//a.pre=max(q.pre,q.val+e.pre);
//a.suf=max(e.suf,e.val+q.suf);原始合并方程
//a.sub=max(max(q.sub,e.sub),q.suf+e.pre);
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define R register
#define LL long long int
using namespace std;
const int N = 5e5+5 ;
LL n,m,d[N],num;
struct Tree{
LL pre,suf,sub,val,lch,rch,ll,rr;//前缀 后缀 最大字段和 区间和 左区间 右区间
}tree[N<<2];
inline void init(){
memset(d,0,sizeof(d));
memset(tree,0,sizeof(tree));
}
inline Tree update(Tree q,Tree e,int pos){
Tree a;
a.pre=a.suf=a.sub=a.val=0;a.val=q.val+e.val;//前缀
if((q.val+e.pre)<=q.pre){
a.pre=q.pre;
a.ll=q.ll;
}
else//前缀
{
a.pre=q.val+e.pre;
a.ll=e.ll;
}
if((e.val+q.suf)>=e.suf){//后缀
a.suf=e.val+q.suf;
a.rr=q.rr;
}
else//后缀
{
a.suf=e.suf;
a.rr=e.rr;
}
if((q.sub>=e.sub)&&(q.sub>=q.suf+e.pre)){//字段和
a.sub=q.sub;
a.lch=q.lch;
a.rch=q.rch;
}
else
if((q.suf+e.pre>=q.sub)&&(q.suf+e.pre>=e.sub))//字段和
{
a.sub=q.suf+e.pre;
a.lch=q.rr;
a.rch=e.ll;
}
else//字段和
{
a.sub=e.sub;
a.lch=e.lch;
a.rch=e.rch;
}
return a;
}
inline void build(R int p,R int l,R int r){
if(l==r){
tree[p].pre=tree[p].suf=tree[p].sub=tree[p].val=d[l];
tree[p].ll=tree[p].rr=tree[p].lch=tree[p].rch=l;
return;
}
R int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tree[p]=update(tree[p<<1],tree[p<<1|1],p);
}
inline Tree query(R int p,R int l,R int r,R int x,R int y){
R Tree q,e,w;
R int pd1=0,pd2=0;
if(l>=x&&r<=y)
{
return tree[p];
}
R int mid=(l+r)>>1;
if(x<=mid){
q=query(p<<1,l,mid,x,y);
pd1=1;
}
if(y>mid){
e=query(p<<1|1,mid+1,r,x,y);
pd2=1;
}
if(pd1&&pd2)w=update(q,e,p);
else if(pd1)w=q;
else if(pd2)w=e;
return w;
}
int main(){
while(~scanf("%lld%lld",&n,&m)){
init();
num++;
printf("Case %lld:\n",num);
for(R int i=1;i<=n;i++)
scanf("%lld",&d[i]);
build(1,1,n);
for(R int i=1;i<=m;i++){
R int a,b;
R Tree c;
scanf("%d%d",&a,&b);
c=query(1,1,n,a,b);
printf("%lld %lld\n",c.lch,c.rch);
}
}
}如果你还是无法调对程序，我这有对拍用的随机数代码：
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
int main() {
freopen("test.in","w",stdout);
srand((unsigned)time(NULL));
int T = rand()%5 + 1;
while(T--) {
int n = rand()%10+1,m = rand()%5+1;
printf("%d %d\n",n,m);
for(int i = 1; i <= n; i++)
if(rand()%2){
printf("%d ",rand()%100);
}else printf("%d ",-rand()%100);
printf("\n");
for(int i = 1; i <= m; i++) {
int l = rand()%n+1,r = rand()%n+1;
if(l>r) swap(l,r);
printf("%d %d\n",l,r);
}
}
return 0;
}