线段树
题解都是清一色的二分答案,提供一个带懒标记的线段树版本。
将原问题转化为
1. 每次将一个区间的元素整体增加一个常量
2. 求某个区间的最小值(对于本题而言就是整个区间)
这就可以用带懒标记的线段树进行处理了。
时间复杂度 $O(m \log n + n)$
代码亲测在luogu可以A,在ACW最后一个点TLE。wwwwww
订正 lazy和mi 可以不用long long,改成int也过了~
C++ 代码
#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;
typedef tuple<int, int, int> aa;
typedef int LL;
constexpr int N = 1e6 + 5;
struct Node {
int l, r;
LL lazy;
LL mi;
}tr[N << 2];
LL d[N];
int q[N];
int l[N], r[N], cnt[N];
int n, m;
inline
void pushup(int u) {
tr[u].mi = min(tr[u << 1].mi, tr[u << 1 | 1].mi);
}
inline
void eval(int u, LL t) {
tr[u].lazy += t;
tr[u].mi += t;
}
inline
void pushdown(int u) {
if (tr[u].lazy == 0) return ;
eval(u << 1, tr[u].lazy);
eval(u << 1 | 1, tr[u].lazy);
tr[u].lazy = 0;
}
void build(int u, int l, int r) {
tr[u].l = l;
tr[u].r = r;
tr[u].lazy = 0;
if (l == r) {
tr[u].mi = q[l];
return;
} else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, LL c) {
if (tr[u].l >= l && tr[u].r <= r) {
eval(u, c);
return;
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, c);
if (r > mid) modify(u << 1 | 1, l, r, c);
pushup(u);
}
}
inline
LL query() {
return tr[1].mi;
}
LL query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].mi;
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL ans = 2e18;
if (l <= mid) ans = min(ans, query(u << 1, l, r));
if (r > mid) ans = min(ans, query(u << 1 | 1, l, r));
return ans;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> q[i];
for (int i = 1; i <= m; i ++) {
cin >> cnt[i] >> l[i] >> r[i];
}
build(1, 1, n);
for (int i = 1; i <= m; i ++) {
modify(1, l[i], r[i], -cnt[i]);
if (query() < 0) {
cout << -1 << '\n' << i;
return 0;
}
}
cout << 0;
return 0;
}
刚才弹幕看到说开o2最后一个样例就过了
谢谢~, 刚把这里的long long 改成int 也A了~