题目链接[https://www.luogu.com.cn/problem/P1083]
题意：
给定一定数目的教室，每个教室都会有固定的位子数量。每天都会有同学去借教室（l - r区间的教室借一定数量的位置），什么时候第一次出现某个教室的位置不能满足同学的需求。
思路，第一次出现，很容易想到二分，我们如何进行二分，首先教室不能满足需求，说明某个教室的板凳数目已经出现了负数，所以我们先把所有的方案全部加上去，再暴力枚举是否出现了负数。
每个方案都是一个区间修改操作，所以我们可以采用前缀和+差分的方式去进行修改操作，大大优化时间。
时间复杂度（O((m + n)logn))
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>using namespace std ;const int N = 1e6 + 10 ;int n , m ;
int w[N] ;
int b[N] , ck[N] ;
int need[N] , L[N] , R[N] ;bool check(int x)
{
memcpy(ck , b , sizeof ck) ;for(int i = 1 ; i <= x ; i ++)ck[L[i]] -= need[i] , ck[R[i] + 1] += need[i] ;int sum = 0 ;for(int i = 1 ; i <= n ; i ++){
sum += ck[i] ;if(sum < 0) return false ;}return true ;
}
int main(void)
{
scanf("%d%d" , &n , &m) ;for(int i = 1 ; i <= n ; i ++) scanf("%d" , &w[i]) ;for(int i = 1 ; i <= n ; i ++) b[i] = w[i] - w[i - 1] ;for(int i = 1 ; i <= m ; i ++)scanf("%d%d%d" , &need[i] , &L[i] , &R[i]) ;int l = 0 , r = n ;while(l < r){
int mid = l + r + 1 >> 1 ;if(check(mid)) l = mid ;else r = mid - 1 ;}if(r == n)puts("0") ;else{
printf("-1\n%d" , l + 1) ;}
}