[Luogu] P1083 [NOIP2012 提高组] 借教室（差分）

一开始用线段树做的，后来还听说能二分+差分？！ 线段树解法
说到差分真是气人，今天耗死在一道查分的字符串计数的题目上了。关于差分
定义差分数组dif[]，dif[i]=a[i]-a[i-1]。如果要对[L,R]每个数加k并且需要单点查询，只要dif[L]+=k，dif[R+1]-=k。单点查询对dif数组求和实现，时间复杂度$O(n)$
总而言之，差分可以实现$O(1)$区间加减，$O(n)$单点查询。

完整代码：

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 1e6+5;

using namespace std;

int n,m,l,r,ans;
int a[maxn],dif[maxn],s[maxn],e[maxn],d[maxn];

int check(int x)
{
    
	memset(dif,0,sizeof(dif));
	for (int i=1; i<=n; i++) dif[i]=a[i]-a[i-1];
		
	for (int i=1; i<=x; i++)
	{
    
		dif[s[i]]-=d[i];
		dif[e[i]+1]+=d[i];
	}
	
	int sum=0;
	for (int i=1; i<=n; i++)
	{
    
		sum+=dif[i];
		if (sum<0) return 1;
	}
	return 0;
}

int main()
{
    
   	FAST; 
	cin>>n>>m;
	for (int i=1; i<=n; i++) cin>>a[i];
	
	for (int i=1; i<=m; i++) cin>>d[i]>>s[i]>>e[i];
	
	l=0, r=n+1;
	int flag=1;
	while(l<=r)
	{
    
		int mid=(l+r)/2;
		if (check(mid))
		{
    
			flag=0;
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	if (flag==0)
	{
    
		cout<<-1<<endl;
		cout<<ans<<endl;
	}
	else cout<<0<<endl;

return 0;
}