原题链接：https://www.luogu.org/problem/show?pid=1083
坐在我对面的dalao瞬间就写出了线段树的解法，蒟蒻线段树太弱，只能写前缀和。
大致分析了一下，二分答案每天能否能满足当天的需求，能就向后找，不能就向前找，
找到最后都能满足，那就是能满足了，不然，此时就会停留在第一个不能满足的时刻。
（终于会用插入代码的操作了（我太弱了。。。））
#include<cstdio> #include<cstring> using namespace std; void read(int &y) { y=0;char x=getchar(); while(x<‘0‘||x>‘9‘) x=getchar(); while(x>=‘0‘&&x<=‘9‘) { y=y*10+x-‘0‘; x=getchar(); } } int n,m,d[1000005],s[1000005],t[1000005]; int sum[1000005],a[1000005]; int check(int x) { memset(sum,0,sizeof(sum)); for(int i=1;i<=x;i++) { sum[s[i]]-=d[i]; sum[t[i]+1]+=d[i]; } for(int i=1;i<=n;i++) { sum[i]+=sum[i-1]; if(a[i]+sum[i]<0) return 0; } return 1; } int main() { read(n);read(m); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<=m;i++) { read(d[i]); read(s[i]); read(t[i]); } int l=1,r=m,mid; while(l<r) { mid=(l+r)>>1; if(check(mid)==0) r=mid; else l=mid+1; } if(r==m) printf("0"); else printf("-1\n%d",r); return 0; }
原文：http://www.cnblogs.com/zeroform/p/7544621.html