@[ThinkofBlank](/space/show?uid=81847) AKWC的巨佬救救我QAQ
by 引领天下 @ 2019-01-24 22:11:49
> @[引领天下](/space/show?uid=39863) 能用线段树写的东西尽量用分块
by arfa @ 2019-01-24 22:22:12
@[arfa](/space/show?uid=77760) ~~不会~~
by 引领天下 @ 2019-01-24 22:23:15
@[引领天下](/space/show?uid=39863) 这种~~假装很难~~的题能用二分，何乐而不为？
by 梧桐灯 @ 2019-01-24 22:23:59
@[光随影走](/space/show?uid=31193) 主要是来练线段树的QAQ
by 引领天下 @ 2019-01-24 22:26:45
@[水军带你飞](/space/show?uid=50558) 救救我
by 引领天下 @ 2019-01-25 17:27:53
@[ThinkofBlank](/space/show?uid=81847) @[水军带你飞](/space/show?uid=50558) 不用了A了，谢谢
by 引领天下 @ 2019-01-25 18:59:03
第一次知道萌新还会写线段树
果然是
奆老
by Grussg @ 2019-01-28 17:09:54
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
long long mi[4000005],add[4000005],R[1000005];
void build(int k,int l,int r)
{
if(l==r)
{
mi[k]=R[l];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
mi[k]=min(mi[k<<1],mi[k<<1|1]);
return ;
}
inline void Add(int k,int l,int r,int v){
add[k]+=v;
mi[k]-=v;
}
void pushdown(int k,int l,int r,int mid)
{
if(add[k]==0) return;
Add(k<<1,l,mid,add[k]);
Add(k<<1|1,mid+1,r,add[k]);
add[k]=0;
return ;
}
void modify(int k,int l,int r,int x,int y,int v)
{
if(x>r or y<l)return;
if(x<=l&&y>=r) return Add(k,l,r,v);;
int mid=(l+r)>>1;
pushdown(k,l,r,mid);
modify(k<<1,l,mid,x,y,v);
modify(k<<1|1,mid+1,r,x,y,v);
mi[k]=min(mi[k<<1],mi[k<<1|1]);
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&R[i]);
build(1,1,n);
int x;
int y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
modify(1,1,n,y,z,x);
if(mi[1]<0)
{
printf("-1\n%d\n",i);
return 0;
}
}
cout<<"0"<<endl;
return 0;
}
```
by 编程协会主 @ 2019-02-02 08:46:26
线段树秒过
by 编程协会主 @ 2019-02-02 08:46:41