这题，第一眼：区间加，区间最小值。这不是线段树裸题吗？
看数据范围 n≤5000000 .开了个tr维护最小值，laz维护加
然后一算空间大概是 152 MB，完了, MLE 。
换方法吧，但是我就想写线段树，就是写线段树才能使我快乐，我就改变策略
本来直接输出 tr[1]，我现在删掉 laz ，让 tr 维护加，访问的时候就访问每个叶子
结点，并且一路下放，原来的值用一个n大小的数组维护，叶子结点的值就是
tr[k]+a[l] 这不就解决空间问题了么,然后只写个 change ， down和 ask 不就完了
代码，最慢的也才 424ms
#include<iostream> #include<cstdio> #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define ls k<<1 #define rs k<<1|1 #define mid ((l+r)>>1) using namespace std; const int maxn=5000005; int n,m,a[maxn]; int tr[maxn<<2]; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){s=s*10+ch-‘0‘;ch=getchar();} return s*w; } inline void down(int k){ tr[ls]+=tr[k];tr[rs]+=tr[k]; } void change(int k,int l,int r,int x,int y,int val){ if(l==x&&y==r){ tr[k]+=val; return ; } if(y<=mid)change(lson,x,y,val); else if(x>mid)change(rson,x,y,val); else change(lson,x,mid,val),change(rson,mid+1,y,val); } int ask(int k,int l,int r){ if(l==r){ return a[l]+tr[k]; } if(tr[k])down(k); return min(ask(lson),ask(rson)); } int main(){ n=read();m=read(); for(int i=1;i<=n;++i) a[i]=read(); int x,y,z; while(m--){ x=read();y=read();z=read(); change(1,1,n,x,y,z); } printf("%d",ask(1,1,n)); return 0; }
原文：https://www.cnblogs.com/sanjinliushi/p/11568894.html