题解 P2367 【语文成绩】
流逝丶
2019-09-20 21:24:18
这题，第一眼：区间加，区间最小值。这不是线段树裸题吗？
看数据范围 $n\le5000000$.开了个tr维护最小值，laz维护加
然后一算空间大概是$152$MB，完了,$MLE$。
换方法吧，但是我就想写线段树，就是写线段树才能使我快乐，我就改变策略
本来直接输出$tr[1]$，我现在删掉$laz$，让$tr$维护加，访问的时候就访问每个叶子
结点，并且一路下放，原来的值用一个n大小的数组维护，叶子结点的值就是
$tr[k]+a[l]$ 这不就解决空间问题了么,然后只写个$change$，$down$和$ask$不就完了
代码，最慢的也才$424ms$
```cpp
#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;
}
```