本文共 1540 字，大约阅读时间需要 5 分钟。

一开始做这个题目的时候，一直想不出来，怎么用线段树来进行维护信息

看了大佬们的代码后，终于知道怎么弄了 好菜啊我 很高兴，又学习了一种线段树的新姿势

首先线段树结构体中维护这几个信息：

结点区间中a的最大值 - maxa 结点区间中b的最小值 - minb 结点区间的延迟更新标记 - addv 结点区间的值 - cnt

每次更新区间 [L,R]

当区间 [L,R] 包含 线段树某个结点的区间时 我们是否要更新该结点的全部孩子结点呢？肯定是不要的，不然复杂度也接受不了 首先我们要更新该结点的maxa 当该结点更新后的maxa还是小于该结点的minb,就不需要更新该结点的孩子结点，只需要延迟更新标记addv更新一下即可，因为该结点的值 cnt 不可能要更新啊 还有就是当该结点没有孩子结点，也就是该结点是叶子结点时，不需要进行下一步更新，并且当叶子结点的maxa不小于minb,说明叶子结点的值cnt要更新了，并且叶子结点的minb要变成minb+b[ind] ,ind为叶子结点代表的点，这些地方得自己好好想一想，我觉得很妙，这种方法

这样线段树就可以维护这个题目的信息了

要是还是不太懂，就看代码吧，我也是看代码看懂的

详细请看代码：

#include
   
    using namespace std;#define max(a,b) a>b?a:b#define min(a,b) a
    
     >1;	Build(l,mid,root<<1);    Build(mid+1,r,root<<1|1);	PushUp(root); } inline void Update(int l,int r,int L,int R,int root){		if(L<=l && R>=r){				tree[root].maxa++;		if(tree[root].maxa
     
      =tree[root].minb){						tree[root].cnt++;			tree[root].minb+=b[l];			return ;		}		if(l==r) return ;	}	PushDown(root);	int mid=(l+r)>>1;	if(L<=mid) Update(l,mid,L,R,root<<1);	if(R>mid) Update(mid+1,r,L,R,root<<1|1);	PushUp(root);}inline int Query(int l,int r,int L,int R,int root){		if(L<=l && R>=r){				return tree[root].cnt;	}	PushDown(root);	int mid=(l+r)>>1;	int ans=0;	if(L<=mid) ans+=Query(l,mid,L,R,root<<1);	if(R>mid) ans+=Query(mid+1,r,L,R,root<<1|1);	return ans; }int main(){		int n,q;	char ch[20];	int l,r;	while(scanf("%d%d",&n,&q)==2){				for(int i=1;i<=n;i++) scanf("%d",&b[i]);		Build(1,n,1);				while(q--){			scanf("%s %d %d",ch,&l,&r);			if(ch[0]=='a') Update(1,n,l,r,1);			else printf("%d\n",Query(1,n,l,r,1));		}	}}
     
    
   

转载地址：https://kaven.blog.csdn.net/article/details/81212708 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！