[luogu] p1083 [noip2012 improvement group] classroom borrowing (difference)

I started with a line segment tree , Later I heard that I could score two points + Difference ？！ Line segment tree solution
Speaking of difference is really annoying , Today, I spent a lot of time on the problem of string counting for score checking . About difference
Define differential array dif[],dif[i]=a[i]-a[i-1]. If you want to [L,R] Add... To each number k And you need a single point of inquiry , as long as dif[L]+=k,dif[R+1]-=k. Single point query pair dif Array summation implementation , Time complexity $O(n)$
To make a long story short , Difference can be achieved $O(1)$ Interval addition and subtraction ,$O(n)$ Single point query .

Complete code ：

#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;
}