应该是算比较简洁的代码了，想学**线段树**的朋友可以参考参考。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define L(a) (a<<1)
#define R(a) (a<<1|1)
using namespace std;
inline int min(int a,int b) { return a<b?a:b; }
inline int max(int a,int b) { return a>b?a:b; }
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
struct Node {
int Le, Re;
int Min;
int Lazy;
}s[4000005];
int n, m, cnt=0;
bool flag=true;

void Build_tree(int p, int l, int r) {
s[p].Le = l; s[p].Re = r;
s[p].Lazy = 0;
if(l == r) {
s[p].Min = read();
return;
}
int mid = (l + r) >> 1;
Build_tree(L(p), l, mid);
Build_tree(R(p), mid+1, r);
s[p].Min = min(s[L(p)].Min, s[R(p)].Min);
}

void Pushdown(int p) {
if(s[p].Le == s[p].Re || s[p].Lazy == 0) return;
s[L(p)].Lazy += s[p].Lazy;
s[R(p)].Lazy += s[p].Lazy;
s[L(p)].Min -= s[p].Lazy;
s[R(p)].Min -= s[p].Lazy;
s[p].Lazy = 0;
s[p].Min = min(s[L(p)].Min, s[R(p)].Min);
}

void Modify(int p, int l, int r, int d) {
Pushdown(p);
if(s[p].Le==l && s[p].Re==r) {
s[p].Lazy += d;
s[p].Min -= d;
if(s[p].Min < 0) flag = false;
return;
}
int mid = (s[p].Le + s[p].Re) >> 1;
if(r <= mid) Modify(L(p), l, r, d);
else if(l > mid) Modify(R(p), l, r, d);
else {
Modify(L(p), l, mid, d);
Modify(R(p), mid+1, r, d);
}
s[p].Min = min(s[L(p)].Min, s[R(p)].Min);
}

int main() {
n=read(); m=read();
Build_tree(1, 1, n);
while((++cnt) <= m) {
int _d=read(), _l=read(), _r=read();
Modify(1, _l, _r, _d);
if(!flag) break;
}
if(flag) printf("0");
else printf("-1\n%d", cnt);
}
```

应该是算比较简洁的代码了，想学**二分**的朋友可以参考参考。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct APP {
    int d, s, t;
}a[1000005];
int n, m;
int r[1000005];
LL c[1000005];

void Input() {
    n=read(); m=read();
    for(int i=1; i<=n; i++) r[i] = read();
    for(int i=1; i<=m; i++) {
        a[i].d = read();
        a[i].s = read();
        a[i].t = read();
    }
}

bool OK(int bd) {
    memset(c, 0, sizeof(c));
    for(int i=1; i<=bd; i++) {
        c[a[i].s] += (LL)a[i].d;
        c[a[i].t+1] -= (LL)a[i].d;
    }
    for(int i=1; i<=n; i++) {
        c[i] += c[i-1];
        if(c[i] > r[i]) return false;
    }
    return true;
}

void Solve() {
    int l=1, r=m;
    while(l <= r) {
        int mid = (l+r) >> 1;
        if(OK(mid)) l = mid + 1;
        else r = mid - 1;
    }
    printf("-1\n%d", l);
}

int main() {
    Input();
    if(OK(m)) printf("0");
    else Solve();
    return 0;
}

二分，check部分应该还可以用前缀和优化时间，不过既然都AC了我也懒得改了
```c++
#include<iostream>
#include<cstdio>
using namespace std;

const int INF = 1000000000;
const int maxn = 1000000 + 10;

struct Book {
int d, s, t;
Book (int d = 0, int s = 0, int t = 0) : d(d), s(s), t(t) {}
};

int n, m;
int r[maxn], bor[maxn], ret[maxn];
Book books[maxn];

bool check (int mid) {
for (int i = 1; i <= n; i++) bor[i] = ret[i] = 0;
for (int i = 1; i <= mid; i++) {
bor[books[i].s] += books[i].d;
ret[books[i].t] += books[i].d;
}
int room = 0;
for (int i = 1; i <= n; i++) {
room += bor[i];
if (room > r[i]) return false;
room -= ret[i];
}
return true;
}

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &r[i]);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &books[i].d, &books[i].s, &books[i].t);

int L = 0, R = m;
while (L < R) {
int M = L + (R-L+1)/2;
if (check(M)) L = M; else R = M-1;
}
if (L == m) cout << "0\n";
else cout << "-1\n" << L+1 << "\n";
return 0;
}
```

二分比线段树简单多了
c++
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#define LL long long
using namespace std;
int x[1000005],y[1000005],d[1000005],s[1000005],a[1000005];
int n,m;
int check(int q){
memset(s,0,sizeof(s));
for(int i = 1;i <= q;i++){
s[x[i]] += d[i];
s[y[i]+1] -= d[i];
}
int tot = 0;
for(int i = 1;i <= n;i++){
tot += s[i];
if(tot > a[i])
return 0;
}
return 1;
}
int main(){
freopen("classroom.in","r",stdin);
//freopen(" classroom.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);
for(int i = 1;i <= m;i++)
scanf("%d%d%d",&d[i],&x[i],&y[i]);
int l = 1,r = m,ans = 0,mid;
while(l <= r){
mid = (l + r) >> 1;
if(check(mid) == 0){
ans = mid;
r = mid-1;
}
else l = mid+1;
}
if(ans != 0)
printf("-1\n%d",ans);
else printf("0");
return 0;
}


黄学长的方法太6，前缀和+二分。。。
但是我也真没想到要用读入优化，看了前辈们的代码才发现是这里出问题了
不过我在校内的OJ，提交同样的代码，就用了258ms，在这上面破3000ms了，这上面多了九个点

参见黄学长题解，非常简洁
p.s. 为什么不写读入优化就T了一个点，写了就A了。。。= =卡得好紧

懒标记线段树可以过
c++
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,d,s,t;
struct tree
{
int l,r,_min,lazy;
}a[4000100];
void read(int &a)
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
a=x*f;
}
void change_tree(int rank,int l,int r,int num)
{
if(a[rank].lazy!=0)
{
a[rank*2]._min-=a[rank].lazy;
if(a[rank*2].l!=a[rank*2].r) a[rank*2].lazy+=a[rank].lazy;
a[rank*2+1]._min-=a[rank].lazy;
if(a[rank*2+1].l!=a[rank*2+1].r) a[rank*2+1].lazy+=a[rank].lazy;
a[rank].lazy=0;
}
if(a[rank].l>r||a[rank].r<l) return;
if(l<=a[rank].l&&r>=a[rank].r)
{
a[rank]._min-=num;;
if(a[rank].l!=a[rank].r) a[rank].lazy+=num;
return;
}
else
{
change_tree(rank*2,l,r,num);
change_tree(rank*2+1,l,r,num);
a[rank]._min=min(a[rank*2]._min,a[rank*2+1]._min);
}
}
void make_tree(int rank,int l,int r)
{
a[rank].lazy=0;a[rank].l=l; a[rank].r=r;
if(l==r) read(a[rank]._min);
else
{
int mid=(l+r)/2;
make_tree(rank*2,l,mid);
make_tree(rank*2+1,mid+1,r);
a[rank]._min=min(a[rank*2]._min,a[rank*2+1]._min);
}
}
int main()
{
freopen("classroom.out","w",stdout);
freopen("classroom.in","r",stdin);
read(n);read(m);
make_tree(1,1,n);
for(int i=1;i<=m;i++)
{
read(d);read(s);read(t);
change_tree(1,s,t,d);
if (a[1]._min<0)
{
cout<<-1<<endl;
cout<<i<<endl;
return 0;
}
}
cout<<0<<endl;
return 0;
}


没想到怎么二分，就用了线段树+读入优化
//此题普通线段树不加读入优化后三个点会TLE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF=0x3f3f3f3f;
const int N=1000005;
const int M=N<<2;

struct node{
    int left;
    int right;
    int num;
    int lazy;
};

struct segTree{
    node tree[M];
    
    int operator [] (int x){
        return tree[x].num;
    }
    
    void setup(int i){
        tree[i].num=min(tree[i<<1].num,tree[i<<1|1].num);
    }
    
    void setdown(int i){
        if(tree[i].lazy!=0){
            tree[i<<1].num+=tree[i].lazy;
            tree[i<<1].lazy+=tree[i].lazy;
            tree[i<<1|1].num+=tree[i].lazy;
            tree[i<<1|1].lazy+=tree[i].lazy;
            tree[i].lazy=0;
        }
    }
    
    void build(int *A,int root,int begin,int end){
        if(begin==end){
            tree[root].num=A[begin];
            tree[root].left=begin;
            tree[root].right=end;
            tree[root].lazy=0;
        }
        else{
            build(A,root<<1,begin,(begin+end)>>1);
            build(A,root<<1|1,((begin+end)>>1)+1,end);
            setup(root);
            tree[root].left=tree[root<<1].left;
            tree[root].right=tree[root<<1|1].right;
        }
    }
    
    int query(int root,int begin,int end){
        if(tree[root].left>end||tree[root].right<begin)
            return INF;
        if(tree[root].left>=begin&&tree[root].right<=end)
            return tree[root].num;
        setdown(root);
        int ans1=query(root<<1,begin,end);
        int ans2=query(root<<1|1,begin,end);
        return min(ans1,ans2);
    }

    void updata(int root,int begin,int end,int add){
        if(tree[root].left>end||tree[root].right<begin)
            return ;
        if(tree[root].left>=begin&&tree[root].right<=end){
            tree[root].num+=add;
            tree[root].lazy+=add;
            return ;
        }
        setdown(root);
        updata(root<<1,begin,end,add);
        updata(root<<1|1,begin,end,add);
        setup(root);
    }
};

inline void read(int &x) {
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    x=0;
    while(ch<='9'&&ch>='0'){
        x=x*10+ch-'0';
        ch=getchar();
    }
}

segTree ST;
int n,m,R[N],D,S,T;
int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        read(R[i]);
    }
    ST.build(R,1,1,n);
    for(int i=1;i<=m;i++){
        read(D);read(S);read(T);
        ST.updata(1,S,T,-D);
        if(ST.query(1,1,n)<0){
            printf("-1\n%d\n",i);
            return 0;
        }
    }
    printf("0\n");
    return 0;
}

时限卡的好紧啊
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

inline int Read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -f; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 - '0' + ch, ch = getchar(); }
return x * f;
}

const int N = 1e6 + 5;

int n, m, r[N], addv[N << 2], minv[N << 2];

inline void PushUp(int rt) { minv[rt] = min(minv[rt << 1], minv[rt << 1 | 1]); }

inline void PushDown(int rt) {
addv[rt << 1] += addv[rt], minv[rt << 1] += addv[rt];
addv[rt << 1 | 1] += addv[rt], minv[rt << 1 | 1] += addv[rt];
addv[rt] = 0;
}

void Build(int L, int R, int rt) {
if (L == R) {
minv[rt] = r[L];
return;
}
int mid = (L + R) >> 1;
Build(L, mid, rt << 1), Build(mid + 1, R, rt << 1 | 1);
PushUp(rt);
}

inline bool Query(int l, int r, int v, int L, int R, int rt) {
if (l <= L && r >= R) {
addv[rt] -= v;
minv[rt] -= v;
return minv[rt] >= 0;
}
PushDown(rt);
int mid = (L + R) >> 1;
bool res = true;
if (r <= mid) res = Query(l, r, v, L, mid, rt << 1);
else if (l > mid) res = Query(l, r, v, mid + 1, R, rt << 1 | 1);
else res = Query(l, r, v, L, mid, rt << 1) & Query(l, r, v, mid + 1, R, rt << 1 | 1);
PushUp(rt);
return res;
}

int main() {
n = Read(), m = Read();
for (int i = 1; i <= n; i++) r[i] = Read();
Build(1, n, 1);
bool ok = true; int cnt = 0;
while (m--) {
cnt++;
int d, s, t; scanf("%d%d%d", &d, &s, &t);
if (Query(s, t, d, 1, n, 1)) continue;
else { ok = false; break; }
}
if (ok) printf("0\n");
else printf("-1\n%d\n", cnt);
return 0;
}

不要轻信题解，都是套路，，，，
唯有本代码才是真理
是可以A的
c++
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int size=1000006;
inline int read()
{
char ch=getchar();
int data=0;
while(ch<'0'||ch>'9')
ch=getchar();
do
{
data=data*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return data;
}
int n,m,a[size];
int d[size],s[size],t[size];
int g[size],now;
int l,r,mid,ans;
inline bool check()
{
if(now<=mid)
for(int i=now+1;i<=mid;i++)
{
g[s[i]]+=d[i];
g[t[i]+1]-=d[i];
}
else
for(int i=now;i>=mid+1;i--)
{
g[s[i]]-=d[i];
g[t[i]+1]+=d[i];
}
ans=0;
for(int i=1;i<=n;i++)
{
ans+=g[i];
if(ans<=a[i])continue;
else return false;
}
return true;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;i++)
{
d[i]=read();
s[i]=read();
t[i]=read();
}
l=1;r=n;
while(r>l+1)
{
mid=(l+r)/2;
if(check())l=mid;
else r=mid;
now=mid;
}
mid=(l+r)/2;
if(check())l=mid;
else r=mid;
if(r==n)printf("0");
else printf("-1\n%d",r);
return 0;
}


var
n,m,d,s,t:longint;
a,tr,g:array[0..1000000+1]of longint;
q:array[0..1000000+1,1..3]of longint;
procedure add(i,x:longint);
var
j:longint;
begin
j:=i;
while j<=n do
begin
tr[j]:=tr[j]+x;
j:=j+j and -j;
end;
end;
function find(i:longint):longint;
var
x,j:longint;
begin
x:=0;
j:=i;
while j>0 do
begin
x:=x+tr[j];
j:=j-j and -j;
end;
exit(x);
end;
procedure main2;
var
i,j:longint;
begin
for i:=1 to m do read(q[i,1],q[i,2],q[i,3]);
for i:=1 to m do
begin
add(q[i,2],q[i,1]);
add(q[i,3]+1,-q[i,1]);
end;
fillchar(g,sizeof(g),0);
for i:=1 to n do
if find(i)>a[i] then begin inc(g[0]); g[g[0]]:=i; end;
if g[0]=0 then begin writeln(0); exit; end;
fillchar(tr,sizeof(tr),0);
for i:=1 to m do
begin
add(q[i,2],q[i,1]);
add(q[i,3]+1,-q[i,1]);
for j:=1 to g[0] do
if find(g[j])>a[g[j]] then begin writeln(-1); writeln(i); exit; end;
end;
end;
procedure main;
var
i,j:longint;
begin
for i:=1 to m do
begin
read(d,s,t);
for j:=s to t do
begin
if a[j]<d then begin writeln(-1); writeln(i); exit; end
else a[j]:=a[j]-d;
end;
end;
writeln(0);
end;
procedure init;
var
i:longint;
begin
read(n,m);
for i:=1 to n do read(a[i]);
if (n<=1000)and(m<=1000) then main//直接模拟
else main2;//树状数组
end;
begin
assign(input, 'classroom.in');
assign(output,'classroom.out');
reset(input);
rewrite(output);
init;
close(input);
close(output);
end.