[小白逛公园]|[SP1716]|[UVA1400]解题报告(三合一)

本文主要是介绍[小白逛公园]|[SP1716]|[UVA1400]解题报告(三合一)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

其实小白逛公园和SP1716是一道题，UVA1400是升级版....都是线段树

题目链接：

1.小白逛公园（这有题面）

2.SP1716 GSS3 - Can you answer these queries III（裸题意在这）

3.UVA1400 "Ray, Pass me the dishes!"

题意：

$n 个数，$

操作0 x y把 $A_x 修改为y$

操作1 l r询问区间

常识数据范围。

思路：这题难在合并，单点修改很容易。我们可以分类讨论，一个区间的最大子段和会从3部分更新过来：

1.左子树的最大子段和。2.右子树的最大子段和。3.跨越左右子树的最大子段和。

前两种情况很容易，直接更新即可，考虑第三种情况怎么更新。

我们开一个结构体

struct Tree{ll pre,suf,sub,val;
}tree[N];

pre为当前区间的最大前缀和，suf为当前区间的最大后缀和，sub为当前区间的最大子段和，val为当前区间的和。

可以发现，第三种情况为左子树的最大后缀和+右子树的最大前缀和。

合并操作分析完毕，接下来只要考虑怎么让代码优雅了.

合并操作代码：

inline Tree push_up(R Tree q,R Tree e){//左子树   右子树Tree w;w.pre=max(q.pre,q.val+e.pre);w.suf=max(e.suf,e.val+q.suf);w.sub=max(max(q.sub,e.sub),q.suf+e.pre);w.val=q.val+e.val;return w;
}

还要注意一点，询问的时候，若左右子树只有一个访问到了，一定不能将两个直接合并，因为另一个没有访问的区间不属于这次询问的范围。

询问操作代码：

inline Tree query(R int p,R int l,R int r,R int x,R int y){R Tree w,q,e;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=push_up(q,e);else if(pd1)w=q;else if(pd2)w=e;return w;
}

完整代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define R register
#define ll long long int
using namespace std;
const int N=500005<<2;
ll n,q,a[N];
struct Tree{ll pre,suf,sub,val;
}tree[N];
inline Tree push_up(R Tree q,R Tree e){Tree w;w.pre=max(q.pre,q.val+e.pre);w.suf=max(e.suf,e.val+q.suf);w.sub=max(max(q.sub,e.sub),q.suf+e.pre);w.val=q.val+e.val;return w;
}
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=a[l];return;}R int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);tree[p]=push_up(tree[p<<1],tree[p<<1|1]);
}
inline void update(R int p,R int l,R int r,R int x,R ll k){//A[x]=kif(l==r){tree[p].pre=tree[p].suf=tree[p].sub=tree[p].val=k;return;}R int mid=(l+r)>>1;if(x<=mid)update(p<<1,l,mid,x,k);else update(p<<1|1,mid+1,r,x,k);tree[p]=push_up(tree[p<<1],tree[p<<1|1]);
}
inline Tree query(R int p,R int l,R int r,R int x,R int y){R Tree w,q,e;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=push_up(q,e);else if(pd1)w=q;else if(pd2)w=e;return w;
}
int main(){scanf("%lld",&n);for(R int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);scanf("%lld",&q);for(R int i=1;i<=q;i++){R int pd,x,y;scanf("%d%d%d",&pd,&x,&y);if(pd==0){update(1,1,n,x,y);}else{Tree w;if(x>y)swap(x,y);w=query(1,1,n,x,y);printf("%lld\n",w.sub);}}return 0;
}

View Code

其实这道题的合并还好，只需要取几个max，Uva1400 的合并才叫恶心，

题意：

给出一个长度为n的整数序列D，你的任务是对m个询问做出回答。

对于询问（a,b），需要找到两个下标x和y，

使得a<=x<=y<=b，并且Dx+Dx+1+....+Dy尽量大。

如果有多组满足条件的x和y，x尽量小。

如果还有多个解，y应该尽量小。

这道题的结构体需要记录的东西更多：

struct Tree{LL pre,suf,sub,val,lch,rch,ll,rr;
//     前缀  后缀  最大字段和  区间和 字段和左端点和右端点  前缀和右端点 后缀和左端点     
}tree[N<<2];

为什么要多记录这4个东西？它要求的不是最大子段和，而是最大子段和的左右端点，我们考虑合并的时候需要用到最大子段和，前缀和，后缀和，所以我们需要记录这些。

合并的时候需要分类讨论：

1.在保证最大子段和的前提下，x尽量小的情况下，y也尽量小。

上一道题怎么合并的？取了3个max，总共有7种情况，分类讨论就好了，

麻烦...

合并代码：

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;}elseif((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;
}

View Code

完整代码：

//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;}elseif((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);}}
}

View Code

如果你还是无法调对程序，我这有对拍用的随机数代码：

#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;
}