借教室

题意

有一个长度为的区间，有次操作，每次使得区间的值减去。

分析

我们每次只需要做两种操作：

1. 询问区间最小值。
2. 使得区间减去。

线段树模板。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 1001110;
const int M = 1e9+7;
int n,m;

int a[maxn];

struct tree_node
{
    int l,r,sum,lazy;
};

struct segtree
{
    tree_node t[maxn*4];
    void pushup(int k)
    {
        t[k].sum = min(t[k*2].sum,t[k*2+1].sum);
    }
    void pushdown(int k)
    {
        if(t[k].lazy)
        {
            t[k*2].lazy += t[k].lazy;
            t[k*2+1].lazy += t[k].lazy;
            t[k*2].sum -= t[k].lazy;
            t[k*2+1].sum -= t[k].lazy;
            t[k].lazy = 0;
        }
    }
    void build(int k,int l,int r)        //建树
    {    
        t[k].l = l,t[k].r = r;
        if(l == r)
        {
            t[k].sum = a[l];
            return;
        }
        int mid = (l+r)/2;
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
        pushup(k);
    }
    void update(int k,int l,int r,int x)        //区间更新
    {  
        if(l > r) return;
        if(l <= t[k].l && t[k].r <= r)
        {
            t[k].sum -= x;
            t[k].lazy += x;
            return;
        }
        pushdown(k);
        if(t[k*2].r >= l) update(k*2,l,r,x);
        if(t[k*2+1].l <= r) update(k*2+1,l,r,x);
        pushup(k);
    }
    int query(int k,int l,int r)            //查询区间最小值
    {
        if(l > r) return 0;
        if(l <= t[k].l && t[k].r <= r)
        {
            return t[k].sum;
        }
        int res = inf;
        pushdown(k);
        if(t[k*2].r >= l) res =  min(res,query(k*2,l,r));
        if(t[k*2+1].l <= r) res = min(res,query(k*2+1,l,r));
        return res;
    }
}st;

vector<int> ans;

signed main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
    }
    st.build(1,1,n);
    int d,s,t;
    for(int i = 1; i <= m; i++)
    {
        cin>>d>>s>>t;
        int mi = st.query(1,s,t);
        if(mi >= d)
        {
            st.update(1,s,t,d);
        }
        else
        {
            cout<<-1<<'\n'<<i<<'\n';
            return 0;
        }
    }
    cout<<0<<'\n';
    return 0;
}