题解：[NOIP2012提高组]借教室

题意

$n$天，$m$个租借订单，第$i$天有$r_i$个教室可用,对于一条租借订单$d_j,s_j,t_j$,代表从天$s_j$到天$t_j$都需要$d_j$个教室，问是否可以满足所有订单，若不满足返回第一个不满足的订单编号

暴力

首先很容易想到用前缀和与差分实现的暴力方法，每次修改差分，再求前缀和判断，这样的算法是$O(n\times m)$

优化

我们希望能压缩到$O(n\ log(m))$或者$O(m\ log(n))$的复杂度，考虑优化找到需要修改订单这一部分

我们假设对于第$x$个订单之前的每个订单都实现

易知性质：若到第$x$个订单没超限，则必有前$x-1$个订单都满足

所以判断一个订单能否被满足，只用修改前$x$次的差分后求前缀和即可，这个很简单

与此同时我们发现这个性质也是单调性的一种，如果第$x$个是满足的那么前面的第$1$到$x$区间的都肯定满足，不满足的订单一定出现在第$x+1$到$n$区间里或者是不存在；同理如果第$x$不满足，其余更优的不满足的订单一定在第$1$到$x$区间或者不存在

因此我们可以考虑使用二分，二分每一个订单

若这个订单可以满足，往右边继续查找订单即可，遇到不满足的时候保存答案，往左边查找

得到$O(n\ log(m))$的算法

代码

#include <bits/stdc++.h>
#define endl '\n'
#define rep_a(i,n) for(int i=1;i<=(n);i++) //正
#define rep_b(i,n) for(int i=n;i>=1;i--) //逆
#define ll long long
#define ull unsigned long long
using namespace std;
const ll MAXN=2e6+5;
struct A{ll d,s,t;}a[MAXN];//订单
ll r[MAXN],diff[MAXN],s[MAXN];
ll n,m;
ll maxa(ll x,ll y){return x>y?x:y;}
ll mina(ll x,ll y){return x>y?y:x;}
bool check(int x){
	memset(diff,0,sizeof(diff));
	memset(s,0,sizeof(s));
	rep_a(i,x){
		diff[a[i].s]+=a[i].d;
		diff[a[i].t+1]-=a[i].d;
	}
	rep_a(i,n){
		s[i]=s[i-1]+diff[i];
		if(s[i]>r[i]){return 0;}
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	rep_a(i,n){cin>>r[i];}
	rep_a(i,m){cin>>a[i].d>>a[i].s>>a[i].t;}
	int l=0,r=m,mid,ans=0;
	while(l<=r){
		//TODO
		mid=(l+r)>>1;
		if(check(mid)){
			l=mid+1;
		}else{
			ans=mid;
			r=mid-1;
		}
	}
	if(ans==0){cout<<ans;return 0;}
	cout<<-1<<endl<<ans;
	return 0;	
}