题面
思路
朴素的想法我们回去暴力修改区间元素，从而判断教室能否够用，但是看数据范围显然这会超时，既然区间问题我们立马想到前缀和和差分数组，and线段树和树状数组，这里不写树状数组和线段树的做法。我们看数据测试量，然后看了一下，这个答案具有线性性质，所以我们可以二分加速，所以我们二分mid，去找不满足条件的最右点，然后在check里面，我们维护一个差分数组，来保存我们要存的教室的数量，最后累加一次前缀和，发现有元素大于原有教室个数，那么我们就判定这个条件下是行不通的。
代码实现
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include<vector>
#include <functional>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int maxn=1000005;
int r[maxn],s[maxn],e[maxn],d[maxn],l,ri,cf[maxn],need[maxn];
int n,m;
bool check (int mid) {
memset (cf,0,sizeof (cf));
for (int i=1;i<=mid;i++) {
cf[s[i]]+=d[i];
cf[e[i]+1]-=d[i];
}
for (int i=1;i<=n;i++) {
need[i]=need[i-1]+cf[i];
if (need[i]>r[i]) return 0;
}
return 1;
}
int main () {
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>r[i];
for (int i=1;i<=m;i++) {
cin>>d[i]>>s[i]>>e[i];
}
l=1,ri=m;
if (check(m)) {
cout<<0<<endl;
return 0;
}
while (l<ri) {
int mid=(l+ri)/2;
if (check(mid)) {
l=mid+1;
}
else ri=mid;
}
cout<<-1<<endl<<l;
return 0;
}