换教室

此题解百分百正解！！！！！！！！

此题巨坑qwq！！！！！！！！！！！！！！！！！

附上连接

传送门（洛谷）

题目描述：

本题先需要一个外层的二分，检测当前订单号是否合法。
差分序列：（可用于区间增减）记录相邻两个量的变化量，所以当在一段区间[l,r]上增加a时，只需要在l处加a，在r+1处-a即可。
我们可以倒起来推，可以把开始那天+租借数量，结束后面的那一天-租借数量

for(int i=1;i<=x;i++)
	{
		day[s[i]]+=d[i];//当s[i]这天需要借教室时加上就行，因为只会对在s~x之间要借用教室的人产生影响，所以可以差分 
		day[t[i]+1]-=d[i];//差分，注意是t[i]+1，因为要包含t[i]这一天也需要用教室 
	}

ok，下面贴出完整代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,m;
int day[maxn],a[maxn],d[maxn],s[maxn],t[maxn];

template <class t> void read(t &x)
{
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}
	x*=f;
}

void readdata()
{
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=m;i++)
	{
		read(d[i]),read(s[i]),read(t[i]);
	}
}

bool check(int x)
{
	memset(day,0,sizeof(day));
	for(int i=1;i<=x;i++)
	{
		day[s[i]]+=d[i];
		day[t[i]+1]-=d[i];
	}
	if(day[1]>a[1]) return true;
	for(int i=2;i<=n;i++)
	{
		day[i]+=day[i-1];//加上之前的day值，维护出这几天要借出去的总数，再与当前天进行比较
		if(day[i]>a[i]) return true;
	}
	return false;
}

void work()
{
	int l=0,r=m,ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid))
		{
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	if(m!=r)
	{
		printf("-1\n");
		printf("%d",ans);
	}
	else printf("0\n");
//	if(ans==0) printf("0");
}

int main()
{
	freopen("input.txt","r",stdin);
	readdata();
	work();
	return 0;
}