hdu5316 Magician(线段树区间合并)

分类：ACM-数据结构

题目：?pid=5316

题意：有n个精灵,每个精灵有一个能力值,有两种操作①改变某一个精灵的能力值②查询区间[L,R]里面位置奇偶相间的能力值的最大和。

分析：这题线段树区间合并可以做。每个节点保存4个信息:①以奇位置开始偶位置结束的奇偶序列最大和②以奇位置开始奇位置结束的奇偶序列最大和③以偶位置开始偶位置结束的奇偶序列最大和④以偶位置开始奇位置结束的奇偶序列最大和

合并的时候,以奇位置开始偶位置结束的奇偶序列最大和=max（lson奇偶,rson奇偶,lson奇偶+rson奇偶,lson奇奇+rson偶偶）;另外三种类似。

查询的时候,返回区间节点并且合并就行了。

代码：

#include <iostream>#include <cstdio>using namespace std;const int maxn = 100000+4;const long long INF = 1e18;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Max(a , b , c , d ) max( max( a , b ) , max( c , d ) )struct node{long long jj,oo,jo,oj;}ans;struct segtree{node tree[maxn<<2];node U(node a,node b){node ret;ret.jj=Max(a.jj , b.jj , a.jo+b.jj , a.jj+b.oj);ret.jo=Max(a.jo , b.jo , a.jo+b.jo , a.jj+b.oo);ret.oj=Max(a.oj , b.oj , a.oj+b.oj , a.oo+b.jj);ret.oo=Max(a.oo , b.oo , a.oj+b.oo , a.oo+b.jo);return ret;}void build(int l,int r,int rt){tree[rt].jj=tree[rt].jo=tree[rt].oj=tree[rt].oo=-INF;if(l==r){if(l&1)scanf("%I64d",&tree[rt].jj);elsescanf("%I64d",&tree[rt].oo);return ;}int m=(l+r)>>1;build(lson);build(rson);tree[rt]=U(tree[rt<<1],tree[rt<<1|1]);}void update(int pos,long long v,int l,int r,int rt){if(l==r){tree[rt].jj=tree[rt].jo=tree[rt].oj=tree[rt].oo=-INF;if(l&1)tree[rt].jj=v;elsetree[rt].oo=v;return ;}int m=(l+r)>>1;if(pos<=m)update(pos,v,lson);elseupdate(pos,v,rson);tree[rt]=U(tree[rt<<1],tree[rt<<1|1]);}node query(int L,int R,int l,int r,int rt){if(L<=l && r<=R)return tree[rt];int m=(l+r)>>1,fg1(0),fg2(0);node Lson,Rson;if(L<=m)Lson=query(L,R,lson),fg1=1;if(R>m)Rson=query(L,R,rson),fg2=1;if(!fg1)return Rson;if(!fg2)return Lson;return U(Lson,Rson);}}T;int main(){int ncase,N,M,tp,x,y;scanf("%d",&ncase);while(ncase–){scanf("%d%d",&N,&M);T.build(1,N,1);while(M–){scanf("%d%d%d",&tp,&x,&y);if(tp==1)T.update(x,y,1,N,1);else{ans=T.query(x,y,1,N,1);printf("%I64d\n",Max(ans.jj,ans.jo,ans.oj,ans.oo));}}}return 0;}

上一篇hdu5335 Walk Out (递推||广搜)下一篇LA3938 "Ray, Pass me the dishes!" (线段树区间合并)

顶0踩0

，如果雨后还是雨，如果忧伤过后还是忧伤，

相关文章：

你感兴趣的文章：

标签云：