小H的询问（线段树）

链接：https://www.nowcoder.com/acm/contest/72/D
来源：牛客网

题目描述

小H给你一个数组{a}，要求支持以下两种操作：

1. 0 l r(1<=l<=r<=n)，询问区间[l,r]中权值和最大的有效子区间的权值和，一个子区间被认为是有效的当且仅当这个子区间中没有两个相邻的偶数或者奇数。

2. 1 x v(1<=x<=n,-109<=v<=109)，将a[x]的值修改为v。
   输入描述:

第一行读入两个正整数n,m(1<=n,m<=105)

第二行读入n个整数，第i个表示a[i](-109 <= a[i] <= 109)

接下来m行，每行三个数表示操作，描述见题目描述。

输出描述:

输出每个询问的答案。

思路：
这道题明显就是一个需要着重处理合并操作的线段树，大体思路很好想出，有两个地方需要注意一个是在查询的的时候我们需要从区间返回多个信息，用结构体的写法比较方便，千万不能调用了除了子树返回的之外的信息，第二就是向上的合并的转移一开始写错了，lsum，和rsum的转移一定要用到sum，把本身就不是连续的区间的sum置为-INF就可以啦
accode

#include
#define LL long long
#define INF 0x3f3f3f3f
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxn = 1e5+332;
int n,m;
LL a[maxn];
struct node
{int l,r;int falg;LL lsum;LL rsum;LL ans;LL sum;node operator +(const node& p) const{node ret;ret.l = l;ret.r = p.r;if((a[r]^a[p.l])&1){//  cout<<"capo"</* if(falg&&p.falg){ret.falg = 1;}else{ret.falg = 0;}*/ret.ans = max(ans,max(p.ans,rsum+p.lsum));ret.sum = sum + p.sum;ret.lsum = max(lsum,sum+p.lsum);ret.rsum = max(p.rsum,p.sum+rsum);//  cout</* if(falg){ret.lsum = max(lsum,lsum+p.lsum);}else{ret.lsum = lsum;}if(p.falg){ret.rsum = max(p.rsum,rsum+rsum);}else{ret.rsum = p.rsum;}*/}else{ret.sum = (LL)maxn*-(LL)INF;//ret.falg = 0;ret.lsum = lsum;ret.rsum = p.rsum;ret.ans = max(ans,p.ans);}return ret;}
}T[maxn<<2];
void push_up(int rt)
{T[rt] = T[lson]+T[rson];
}
void build(int l,int r,int rt)
{//// cout<<"fwfwf"<T[rt].l = l;T[rt].r = r;if(l==r){// cout<<"fang"<T[rt].lsum = T[rt].rsum = T[rt].ans =T[rt].sum= a[l];// T[rt].falg = 1;// cout<// cout<<"fwfwgtafg"<return ;}int mid = (l+r)>>1;build(l,mid,lson);build(mid+1,r,rson);push_up(rt);
}
void update(int rt,int p,LL va)
{if(T[rt].l==T[rt].r&&T[rt].l==p){a[p] = va;T[rt].lsum = T[rt].rsum = T[rt].ans =T[rt].sum = va;//T[rt].falg  = 1;return ;}int mid = (T[rt].l+T[rt].r)>>1;if(p<=mid){update(lson,p,va);}else{update(rson,p,va);}push_up(rt);
}
node query(int rt,int L,int R)
{if(L<=T[rt].l&&R>=T[rt].r){return T[rt];}int mid = (T[rt].l+T[rt].r)>>1;int falg1 = 0;int falg2 = 0;node ret1;node ret2;if(L<=mid){falg1 = 1;ret1 = query(lson,L,R);}if(R>mid){falg2 = 1;ret2 = query(rson,L,R);} if(falg1&&falg2){return ret1+ret2;}else if(falg1&&!falg2){return ret1;}else{return ret2;}
}
int main()
{scanf("%d%d",&n,&m);for(int i = 1;i<=n;i++){scanf("%lld",&a[i]);}//cout<<"fuck"<build(1,n,1);for(int i = 0;iint op;scanf("%d",&op);if(op==0){int l,r;scanf("%d%d",&l,&r);node tmp = query(1,l,r);printf("%lld\n",tmp.ans);}else{int p;LL va;scanf("%d%lld",&p,&va);update(1,p,va);}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！