[//]: # 用线段树写的，正常写线段树的话，时间爆了，就改了一下，用update直接进行判断，节约了查询的时间

题目描述

#include <iostream>

using namespace std;

const int N = 1000006;

int sum[N * 8], add[N * 8];

void push_up(int rt)
{
    sum[rt] = min(sum[rt * 2], sum[rt * 2 + 1]);
}

void push_down(int rt)
{
    if(add[rt])
    {
        sum[rt * 2] = sum[rt * 2] - add[rt];
        sum[rt * 2 + 1] = sum[rt * 2 + 1] - add[rt];
        add[rt * 2] = add[rt * 2] + add[rt];
        add[rt * 2 + 1] = add[rt * 2 + 1] + add[rt];
        add[rt] = 0;
    }
}
void build(int l, int r, int rt)
{
    add[rt] = 0;
    if(l == r)
    {
        scanf("%d", &sum[rt]);
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, rt * 2);
    build(mid + 1, r, rt * 2 + 1);
    push_up(rt); 
}

int update(int a, int b, int c, int l, int r, int rt)
{
    if(a <= l && b >= r)
    {
        sum[rt] = sum[rt] - c;
        add[rt] = add[rt] + c;
        if(sum[rt] < 0)
        return 0;
        else
        return 1;
    }
    int mid = (l + r) / 2;
    push_down(rt);
    if(a <= mid)
    {
        if(update(a, b, c, l ,mid, rt * 2) == 0)
        {
            return 0;
        }
    }
    if(b > mid)
    {
        if(update(a, b, c, mid + 1, r, rt * 2 + 1) == 0)
        {
            return 0;
        }
    }
    push_up(rt);
}

/*int query(int a, int b, int l, int r, int rt)
{
    if(a <= l && b >= r)
    {
        return sum[rt];
    }
    push_down(rt);
    int mid = (l + r) / 2;
    int ans = 0x3f3f3f3f;
    if(a <= mid)
    {
        ans = min(ans, query(a, b, l, mid, rt * 2));
    }
    if(b > mid)
    {
        ans = min(ans, query(a, b, mid + 1, r, rt * 2+ 1));
    }
    return ans;
}*/ 
int main()
{
    int s, t, d, n, m, k;
    scanf("%d%d", &n, &m);
    build(1, n, 1); 
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d",&d, &s, &t);
        if(update(s, t, d, 1, n, 1) == 0)
        {
            printf("-1\n%d\n", i);
            return 0;
        }
    }
    printf("%d\n", 0);

    return 0;
}