本文主要是介绍【线段树 懒惰标记】JZOJ_1380 最大值（新版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
题意：
在一个长度为n的序列里进行两种操作：(1)1 x y c表示把a[x]到a[y]增加c，(2)2 x y表示询问区间[x~y]的最大值。
思路：
这题和1379的差不多，就是第一个操作的时候我们可以先做一个标记，等到查找的时候我们再把标记下传下去，可以使时间得到优化。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{int v,d;
}tree[400500];
int c,x,y,n,m,z,a[100500];
void build(int k,int l,int r)
{if (l==r) {tree[k].v=a[l];return;} int mid=(l+r)>>1;build(2*k,l,mid);build(2*k+1,mid+1,r); tree[k].v=max(tree[2*k].v,tree[2*k+1].v);//建树
}
void inc(int wz,int l,int r,int x,int y,int val)
{if (l==x&&r==y) {tree[wz].d+=val;tree[wz].v+=val;return;}if (tree[wz].d!=0){tree[wz*2].d+=tree[wz].d;tree[wz*2].v+=tree[wz].d;tree[wz*2+1].d+=tree[wz].d;tree[wz*2+1].v+=tree[wz].d;tree[wz].d=0;}int mid=(l+r)>>1;if (y<=mid) inc(wz*2,l,mid,x,y,val);else if (x>mid) inc(wz*2+1,mid+1,r,x,y,val);else {inc(wz*2,l,mid,x,mid,val);inc(wz*2+1,mid+1,r,mid+1,y,val);}tree[wz].v=max(tree[wz*2].v,tree[wz*2+1].v);//进行标记
}
long long find(int wz,int l,int r,int x,int y)
{if (x==l&&y==r) {return tree[wz].v;}if (tree[wz].d!=0)//如果我们查询的这个区间里有修改我们就下传标记{tree[wz*2].d+=tree[wz].d;tree[wz*2].v+=tree[wz].d;tree[wz*2+1].d+=tree[wz].d;tree[wz*2+1].v+=tree[wz].d;tree[wz].d=0;}int mid=(l+r)>>1;if (y<=mid) return find(wz*2,l,mid,x,y);else if (x>mid) return find(wz*2+1,mid+1,r,x,y);else return max(find(wz*2,l,mid,x,mid),find(wz*2+1,mid+1,r,mid+1,y));
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);scanf("%d",&m);while (m--){scanf("%d",&c);if (c==1) {scanf("%d%d%d",&x,&y,&z);inc(1,1,n,x,y,z);}else {scanf("%d%d",&x,&y);printf("%lld\n",find(1,1,n,x,y));}}
}
这篇关于【线段树 懒惰标记】JZOJ_1380 最大值（新版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
