<借教室>题解

什么？ 要用差分， 二分？？？不要欺负蒟蒻啊 QWQQWQ

那就先想一想暴力吧

显然对每个需求，暴力修改，如果超出供给直接输出，得了 4545 分， 如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define clr(a,b)  memset((a),b,sizeof(a))
using namespace std;
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 << 3) + (s << 1) + (ch ^ 48); ch = getchar(); }
    return s * w;
}
const int MX = 5e5 + 50;
int d[MX], t[MX], r[MX], s[MX], N, M, u[MX];
void solve() {
    rep(i, 1, N) {
        rep(j, s[i], t[i]) {
            u[j] += d[i];
            if(u[j] > r[j]) {
                printf("-1\n%d\n", i);
                exit(0);
            }
        }
    }
    puts("0");
}
int main() {
    N = Read(), M = Read();
    rep(i, 1, N) r[i] = Read();
    rep(i, 1, M) d[i] = Read(), s[i] = Read(), t[i] = Read();
    solve();
    return 0;
}

挠头 ing ~ -1s...~-1s....ing −1s... −1s....

啊！

线段树！！！

既然要区间修改，线段树啊！！

我们发现此题只需用线段树维护一下最小值即可，如果区间修改的时候最小值减去当前的需求已经为负，直接输出即可 OvOOvO

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define clr(a,b)  memset((a),b,sizeof(a))
using namespace std;
inline LL Read(){
    LL 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 << 3) + (s << 1) + (ch ^ 48); ch = getchar(); }
    return s * w;
}
const int MX = 2000010;
int t[MX], s[MX], N, M;
LL R[MX],tree[MX * 5], num, flag[MX * 5], d[MX];
void pushup(int now) { tree[now] = min(tree[now << 1], tree[now << 1 | 1]); } 
void Build_tree(int l, int r, int now) {
    if(l == r) {
        tree[now] = R[l];
        return;
    }
    int mid = (l + r) >> 1;
    Build_tree(l, mid, now << 1);
    Build_tree(mid + 1, r, now << 1 | 1);
    pushup(now);
}
void pushdown(int now) {
    if(flag[now]) {
        tree[now << 1] -= flag[now];
        tree[now << 1 | 1] -= flag[now];
        flag[now << 1] += flag[now];
        flag[now << 1 | 1] += flag[now];
        flag[now] = 0;
    }
    return;
}
void updata(int l, int r, int now, int x, int y, LL z) {
    if(x <= l && r <= y) {
        if(tree[now] - z < 0) {
            printf("-1\n%lld\n", num);
            exit(0);
        }
        tree[now] -= z;
        flag[now] += z;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(now);
    if(x <= mid) updata(l, mid, now << 1, x, y, z);
    if(y > mid) updata(mid + 1, r, now << 1 | 1, x, y, z);
    pushup(now);
}
void solve() {
    for(num = 1; num <= M; ++num) updata(1, N, 1, s[num], t[num], d[num]);
    cout << "0" << endl;
}
int main() {
    N = Read(), M = Read();
    rep(i, 1, N) R[i] = Read();
    rep(i, 1, M) d[i] = Read(), s[i] = Read(), t[i] = Read();
    Build_tree(1, N, 1);
    solve();
    return 0;
}

ByBy 飞马の幻想

End~End