借教室--二分+查分

1.不要多开map，很占空间和时间

2.差分体现在占教室，区间的减用差分，区间的加可以模拟翻棋子或者涂油漆什么的

3.二分体现在最大值最小，就是具有单调性，无穷绝对可以的情况，那么从无穷开始二分尝试答案，最终快速找到

P1083 [NOIP 2012 提高组] 借教室 - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
int df[1000002];
int n,m;
int d[1000002];
int s[1000002],t[1000002];
bool check(int x)
{vector<int> dff;dff.push_back(0);for(int i=1;i<=n;i++) dff.push_back(df[i]);for(int i=1;i<=x;i++){dff[s[i]]-=d[i];dff[t[i]+1]+=d[i];}ll s=0;for(int i=1;i<=n;i++){s+=dff[i];if(s<0) return true;}return false;
}
void solve()
{} 
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//solve();cin>>n>>m;int a,b;a=0;for(int i=1;i<=n;i++){cin>>b,df[i]=b-a;a=b;	} for(int i=1;i<=m;i++) cin>>d[i]>>s[i]>>t[i];int l=1,r=m;if(!check(m)){cout<<0;}else{int an;while(l<=r){int mid=(l+r)>>1;if(check(mid)){an=mid;r=mid-1;}else l=mid+1;}cout<<-1<<endl;cout<<an;		}return 0;
}