线段树模板

线段树 区间最大

题目描述

在N个数A1…An组成的序列上进行M次操作，操作有两种：

(1)1 L R C：表示把A[L]到A[R]增加C（C的绝对值不超过10000）；

(2)2 L R：询问A[L]到A[R]之间的最大值。

输入

第一行输入N，表示序列的长度，接下来N行输入原始序列；接下来一行输入M表示操作的次数，接下来M行，每行为1 L R C或2 L R

输出

对于每个操作(2)输出对应的答案。

样例输入

5 1 2 3 4 5 3 2 1 4  1 1 3 3 2 3 5

样例输出

4 6

提示

对于100%的数据满足：1<=N,M,L,R<=100000。所有的数都在int的范围内。

线段树模板

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<iomanip> #include<map> #include<set> #include<vector> #include<queue> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return f*x; } const int N=100010; int n,a[N],q,cnt,ans[N]; struct seg{int mx,plus;}tr[N<<2]; inline void build(int l,int r,int pos) { if(l==r){tr[pos].mx=a[l];return ;} int mid=r+l>>1; build(l,mid,pos<<1);build(mid+1,r,pos<<1|1); tr[pos].mx=max(tr[pos<<1].mx,tr[pos<<1|1].mx); } inline void update(int k) { int t=tr[k].plus; tr[k<<1].plus+=t;tr[k<<1|1].plus+=t; tr[k<<1].mx+=t;tr[k<<1|1].mx+=t; tr[k].plus=0; } inline void modify(int l,int r,int pos,int x,int y,int v) { if(l>=x&&r<=y){tr[pos].mx+=v;tr[pos].plus+=v;return ;} int mid=r+l>>1;update(pos); if(y<=mid)modify(l,mid,pos<<1,x,y,v); else if(x>mid)modify(mid+1,r,pos<<1|1,x,y,v); else modify(l,mid,pos<<1,x,y,v),modify(mid+1,r,pos<<1|1,x,y,v); tr[pos].mx=max(tr[pos<<1].mx,tr[pos<<1|1].mx); } inline int query(int l,int r,int pos,int x,int y) { if(l>=x&&r<=y)return tr[pos].mx; int mid=l+r>>1;update(pos); if(mid>=y)return query(l,mid,pos<<1,x,y); if(mid<x)return query(mid+1,r,pos<<1|1,x,y); else return max(query(l,mid,pos<<1,x,y),query(mid+1,r,pos<<1|1,x,y)); } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); build(1,n,1); int opt,x,y,v; q=read(); for(int i=1;i<=q;i++) { opt=read();x=read();y=read(); switch(opt) { case 1:v=read();modify(1,n,1,x,y,v);break; case 2:printf("%d\n",query(1,n,1,x,y));break; } } return 0; }