Label

简单的二分答案+简单差分数组维护

Description

https://www.luogu.com.cn/problem/P1083

Solution

解法一—线段树

维护区间 r r r数组最小值，每一个订单相当于区间减 d i d_i di​，若某个订单对应的操作使得全局最小值小于 0 0 0，则答案即为该份订单，否则输出0。

解法二—二分答案

此题单调性：订单越多，该订单越有可能无法被满足。

一般来说，二分是个很有用的优化途径，而对于能否二分，有一个界定标准：状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。 对于此题，如果前一份订单都不满足，那么之后的所有订单都不用继续考虑；而如果后一份订单都满足，那么之前的所有订单一定都可以满足，符合局部舍弃性，所以可以二分订单数量。所以，根据这两个性质，对于此题，我们二分检查前 k k k份订单是否可被满足。

问题来了，对于每一个答案 k k k，如何检查前 k k k份订单是否可被满足？

我们易知：对于每一个订单 ( d i , s i , t i ) (d_i,s_i,t_i) (di​,si​,ti​)，相当于使 r s i ∼ r t i r_{s_i}\sim r_{t_i} rsi​​∼rti​​ 全部减去 t i t_i ti​。当对前 i i i组订单执行完此操作后，我们查看所有 r i r_i ri​，若无小于0的值则前 i i i份订单是否可被满足，否则不可被满足。这个操作我们可以用线段树维护（但这样一来直接用解法一做即可，不可取），但我们有更加简便的操作—差分数组。

差分数组支持 O ( 1 ) O(1) O(1)的区间加/减与 O ( n ) O(n) O(n)的单值查询，对于此题，我们设 d i f [ i ] = r [ i ] − r [ i − 1 ] dif[i]=r[i]-r[i-1] dif[i]=r[i]−r[i−1]，对于每组订单 ( d i , s i , t i ) (d_i,s_i,t_i) (di​,si​,ti​)，令 d i f [ s [ i ] ] − = d [ i ] , dif[s[i]]-=d[i], dif[s[i]]−=d[i], d i f [ t [ i ] + 1 ] + = d [ i ] dif[t[i]+1]+=d[i] dif[t[i]+1]+=d[i]；修改完后的 r i = ∑ k = 1 i d i f [ k ] r_i=\sum_{k=1}^{i}dif[k] ri​=∑k=1i​dif[k]，检查其中是否存在大于0的情况即可。

算法复杂度： O ( n l o g n ) O(nlogn) O(nlogn)

最后注意：由于我们实际二分出来的值是“可满足的订单的最大值”，故边界情况需要特判（对于二分答案，任何时候认真考虑上下边界的取值都是必要的）。

Code

#include<cstdio>
#include<iostream>
#define ri register int
using namespace std;

const int MAXN=1e6+20;
int N,M,a[MAXN],d[MAXN],s[MAXN],t[MAXN],l,r,mid,dif[MAXN],ans;

bool check(int sj)
{
	for(ri i=1;i<=N;++i)	
		dif[i]=a[i]-a[i-1];
	for(ri i=1;i<=sj;++i)
	{
		dif[s[i]]-=d[i];
		dif[t[i]+1]+=d[i];
	}
	for(ri i=1;i<=N;++i)
	{
		dif[i]=dif[i-1]+dif[i];
		if(dif[i]<0)	return false;
	}
	return true;
}

int main()
{
	scanf("%d%d",&N,&M);
	for(ri i=1;i<=N;++i) scanf("%d",&a[i]);
	for(ri i=1;i<=M;++i) scanf("%d%d%d",&d[i],&s[i],&t[i]);
	l=1,r=N;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(check(mid))	l=mid;
		else	r=mid-1;
	}
	if(l==1)
	{
		if(check(l))	ans=2;
		else ans=1;
	}
	else if(l==N)
	{
		if(check(l))	ans=N+1;
		else	ans=N;
	}
	else ans=l+1;
	if(ans>N)	cout<<"0";
	else	cout<<"-1"<<'\n'<<ans;
	return 0;
}