刷题记录:牛客NC15162小H的询问

传送门:牛客

题目描述:

小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。
输入:
10 10
-9 -8 -8 -8 2 -7 -5 2 2 3 
0 3 5
0 4 4
0 2 4
1 6 6
1 1 6
1 5 9
0 1 2
1 5 -8
0 2 4
1 3 -2
输出:
2
-8
-8
6
-8

此题题意鲜明,但是维护起来并不简单,解决此题之后感觉对线段树又有了进一步的理解
具体做法和这道题的解法有点相似,建议先去做做那道题再来做此题

首先对于此题,我们用$l,r$来维护区间左右端点
$num[]$数组来维护区间端点的奇偶性,方便区间合并维护
$lmax$来维护区间左端点开始最大的连续权值和
$rmax$来维护区间右端点开始最大的连续权值和
$sum$用来维护区间和,$flag$用来维护该区间是否是有效子区间
$max\_sum$用来维护区间有效子区间的最大权值和

那么对于我们的$pushup$来说,

父亲区间的$num[],sum$维护起来很简单,此处就不在赘述了

对于$max\_sum$来说,有三种情况:
1.可能最大权值的有效区间在左儿子区间 2.可能最大权值在右儿子区间 3.可能最大权值横跨左右儿子区间 .
对于前两种来说,不难解决.对于第三种来说,我们首先需要判断两个儿子区间能否合成一个有效区间(我们可以通过$num[]$区间来进行判断).假设我们能合并成一个区间,那么我们此时横跨的有效区间的最大值显然就是左子树的$rmax$+右子树的$lmax$

对于$lmax$,$rmax$来说,只有两种情况,要么单单只是在一个区间,要么横跨区间.拿$lmax$来说,此时我们的$lmax$要么直接采取左区间的$lmax$,要么取左区间的所有和$sum$+右区间的$lmax$

对于$flag$来说:
我们需要注意的是,不是左区间是有效区间+右区间是有效区间,那么我们的大区间就是有效区间了.我们还需要注意合并问题,我刚开始没注意到这一点,$wa$了无数次

对于$update$来说:

单点修改,比较简单,此处就不在赘述了,具体可以参考代码

对于$query$来说,可以好好体会,本题的点睛之笔所在:

对于$query$来说,我们也有三种情况,跟$pushup$一模一样(做完这道题后,我感觉$query$简直可以说就是$pushup$,就跟$pushdown$其实就是$update$一样)

对于前两种情况,因为是在一个区间里的,而对于一个区间内的所有值我们早已维护好,所以不难实现.复杂的是横跨区间的.此时我们就犯了难了.因为我们发现这种并不是能用我们之前的普通的线段树的$query$模板可以解决的.此时有一个小技巧就是采用我们的$pushup$,我们会发现对于$pushup$来说,我们解决了儿子对父亲的贡献的问题.那么对于横跨左右区间的一个区间来说,我们同样可以先去解决儿子区间的问题,然后使用$pushup$来反馈我们的小区间对大区间的回馈即可.看不懂没关系,可以结合下面的代码,不难理解,但是很妙

个人感觉打完此题的$query$部分后,对线段树的$query$维护变得更加通透了,原来$query$就是不断是$pushup$的过程啊

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{
	int l,r,max_sum,num[2],lmax,rmax,sum,flag;
}tree[maxn*4];
int n,m;int a[maxn];
void pushup(Segment_tree &u,Segment_tree &l,Segment_tree &r) {
	u.sum=l.sum+r.sum;
	u.flag=0;
	u.num[0]=l.num[0];u.num[1]=r.num[1];
	u.lmax=l.lmax;u.rmax=r.rmax;
	u.max_sum=max(l.max_sum,r.max_sum);
	if(l.num[1]^r.num[0]) {
		u.max_sum=max(u.max_sum,l.rmax+r.lmax);
		if(l.flag) u.lmax=max(u.lmax,l.sum+r.lmax);
		if(r.flag) u.rmax=max(u.rmax,r.sum+l.rmax);
		if(l.flag&&r.flag){
			u.flag=1;
			u.sum=l.sum+r.sum;
		}
	}
} 
void pushup(int rt) {
	pushup(tree[rt],tree[ls],tree[rs]);
}
void build(int l,int r,int rt) {
	tree[rt].l=l;tree[rt].r=r;
	if(l==r) {
		tree[rt].sum=tree[rt].max_sum=tree[rt].lmax=tree[rt].rmax=a[l];
		if(a[l]%2==0) tree[rt].num[0]=tree[rt].num[1]=0;
		else tree[rt].num[0]=tree[rt].num[1]=1;
		tree[rt].flag=1;
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);build(rson);
	pushup(rt);
}
void update(int pos,int v,int rt) {
	if(tree[rt].l==pos&&tree[rt].r==pos) {
		tree[rt].sum=tree[rt].max_sum=tree[rt].lmax=tree[rt].rmax=v;
		tree[rt].num[0]=tree[rt].num[1]=(v%2==0?0:1);
		tree[rt].flag=1;
		return ;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(pos<=mid) update(pos,v,ls);
	else update(pos,v,rs);
	pushup(rt);
}
Segment_tree query(int l,int r,int rt) {
	if(tree[rt].l==l&&tree[rt].r==r) {
		return tree[rt];
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(r<=mid) return query(l,r,ls);
	else if(l>mid) return query(l,r,rs);
	else {
		auto Left=query(l,mid,ls);
		auto Right=query(mid+1,r,rs);
		Segment_tree res;
		pushup(res,Left,Right);
		return res;
	}
}
signed main() {
	n=read();m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(root);
	for(int i=1;i<=m;i++) {
		int opt=read();
		if(opt==0) {
			int l=read(),r=read();
			printf("%lld\n",query(l,r,1).max_sum);
		}
		else {
			int x=read(),v=read();
			update(x,v,1);
		}
	}
	return 0;
}