spoj 1716. Can you answer these queries III

本文主要是介绍spoj 1716. Can you answer these queries III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

spoj  1716. Can you answer these queries III

在spoj上做题的时候看到有人提交做这个题目，看名字就知道肯定是数据结构的题目，然后看了看，题意很简单.......然后看了半天也没想到可行的思路，我的思路主要是卡在一段子区间的和可以用sum[ r ] -sum [ l-1]来表示，如过让这个值最大那么贪心就是求给出的[ l , r ]  max(sum[ i])  - min(sum[j ])  i,j在[l,r]区间内的，但是i可能是i < j那么就不适用贪心了，然后就卡在了……想到用线段树，但是就没有往线段树区间和并方面想，看来线段树区间合并真是个神奇的东西！

看的别人的代码才明白的   http://blog.csdn.net/gotoac/article/details/7623857

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int maxn=50010;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
ll lsum[maxn<<2],msum[maxn<<2],rsum[maxn<<2],sum[maxn<<2];
struct Node{ll lsum,msum,rsum,sum;
};
void pushup(int rt)
{int ls=rt<<1,rs=rt<<1|1;lsum[rt]=max(lsum[ls],sum[ls]+lsum[rs]);msum[rt]=max(max(msum[ls],msum[rs]),rsum[ls]+lsum[rs]);rsum[rt]=max(rsum[rs],sum[rs]+rsum[ls]);sum[rt]=sum[ls]+sum[rs];
}
void build(int l,int r,int rt)
{if(l==r){scanf("%lld",&sum[rt]);lsum[rt]=rsum[rt]=msum[rt]=sum[rt];return;}int m=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int p,ll val,int l,int r,int rt)
{if(l==r) {lsum[rt]=msum[rt]=rsum[rt]=sum[rt]=val;return;}int m=(l+r)>>1;if(p<=m) update(p,val,lson);else update(p,val,rson);pushup(rt);
}
Node query(int L,int R,int l,int r,int rt)
{Node ret;if(L<=l&&R>=r){ret.lsum=lsum[rt],ret.msum=msum[rt],ret.rsum=rsum[rt],ret.sum=sum[rt];return ret;}int m=(l+r)>>1;if(R<=m) return query(L,R,lson);if(L>m)  return query(L,R,rson);Node ret1=query(L,R,lson);Node ret2=query(L,R,rson);ret.lsum=max(ret1.lsum,ret1.sum+ret2.lsum);ret.msum=max(max(ret1.msum,ret2.msum),ret1.rsum+ret2.lsum);ret.rsum=max(ret2.rsum,ret2.sum+ret1.rsum);ret.sum=ret1.sum+ret2.sum;return ret;
}
int main()
{int n,m,l,r,cmd;while(scanf("%d",&n)==1){build(1,n,1);scanf("%d",&m);while(m--){scanf("%d%d%d",&cmd,&l,&r);if(cmd==0) update(l,r,1,n,1);else printf("%d\n",query(l,r,1,n,1).msum);}}return 0;
}

这篇关于spoj 1716. Can you answer these queries III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---