从线段树的思路来看就是维护区间最小值，对最小值进行更新，某一次小于0，则输出这次为答案
我的代码:
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1e6 + 10; int n, m, a[N]; struct node { int l; int r; int lz; int w; } tr[N << 2]; void pushdown(int u) { if (tr[u].lz) { tr[u << 1].w -= tr[u].lz; tr[u << 1 | 1].w -= tr[u].lz; tr[u << 1].lz += tr[u].lz; tr[u << 1 | 1].lz += tr[u].lz; tr[u].lz = 0; } } void pushup(int u) { tr[u].w = min(tr[u << 1].w, tr[u << 1 | 1].w); } void build(int u, int l, int r) { tr[u] = {l, r, 0}; if (l == r) { tr[u].w = a[l]; return; } int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } void update(int u, int l, int r, int k) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].w -= k; tr[u].lz += k; return ; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) update(u << 1, l, r, k); if (r > mid) update(u << 1 | 1, l, r, k); pushup(u); return ; } bool query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { if (tr[u].w <0) return false; else return true; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; bool f1 = 1, f2 = 1; if (l <= mid) f1 = query(u << 1, l, r); if (r > mid) f2 = query(u << 1 | 1, l, r); return f1 &f2; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } build(1, 1, n); int d, s, t; bool f = 1; int cnt = 1; for (int T = 1; T <= m; T++) { scanf("%d%d%d", &d, &s, &t); bool ok = true; update(1, s, t, d); ok = query(1, s, t); if (!ok) { f = 0; cout << -1 << "\n"; cout << T << "\n"; break; } } if (f) cout << 0 << "\n"; return 0; }
更快的二分加差分的方法
首先，差分是一种对区间修改的优化，可以把时间复杂度降到只跑一遍
重点是二分，因为对于某个点，如果不满足，那么不满足的点一定是它，或是它的前方的某个点
如果满足，那就一定在后面
其实是单调的
就可以用二分来做:
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,c[N],d[N],t[N],s[N],r[N]; inline bool check(int x) { memset(c,0,sizeof c); for(int i=1;i<=x;i++) { c[s[i]]+=d[i]; c[t[i]+1]-=d[i]; } for(int i=1;i<=n;i++) { c[i]+=c[i-1]; if(c[i]>r[i]) return true; } return false; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&r[i]); } for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i],&s[i],&t[i]); if(!check(m)) { cout<<0<<"\n"; return 0; } int l=0,r=m; while(l<r) { int mid=l+r>>1; if(check(mid)) r=mid;//chushi else l=mid+1; } printf("-1\n%d\n",l); }
