题意：n天每天有n个教室
m条申请，每个要求在$a_i$到$b_i$天占用$c_i$间教室
问最早无法满足的申请序号
全能满足输出0
二分+差分前缀和
错解：将每天的教室差分，然后在二分判断成立时，把1--now-1的申请在差分数组上处理，然后看看能不能满足now
然而。。。。这是错的
因为当前这个可以，也许前面有一个就不可以，而此时是默认前面都可以了 ，这是不单调的
正解：开一个空的差分数组进行差分，之后对于1---now每一个询问在数组上操作
然后枚举每一天，如果当天数量+借走的<0说明1---now有一天不满足，我们不管是哪一天，因为二分迟早会找到，而且，这样是单调的，可以二分（判断的是1---now而不是now自己！！！）
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define olinr return #define _ 0 #define love_nmr 0 #define DB double #define nmr 1050500 int a[nmr]; int ls[nmr]; int n; int m; struct node { int s,t; int dis; }; node p[nmr]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } inline bool ok(int mid) { int tot=0; memset(ls,0,sizeof ls); for(int i=1;i<=mid;i++) { ls[p[i].s]-=p[i].dis; ls[p[i].t+1]+=p[i].dis; } for(int i=1;i<=n;i++) { tot+=ls[i]; if(a[i]+tot<0) return true; } return false; } signed main() { n=read(); m=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=m;i++) { p[i].dis=read(); p[i].s=read(); p[i].t=read(); } int l=1; int ans; int r=m; if(!ok(m)) { put(0); olinr ~~(0^_^0)+love_nmr; } while(l<=r) { int mid=(l+r)>>1; if(ok(mid)) { ans=mid; r=mid-1; } else l=mid+1; } put(-1); putchar(' '); put(ans); olinr ~~(0^_^0)+love_nmr; }