Flandre Scarlet's Blog

前缀&差分大法好。

SHC太大了：线段树维护区间最小值和Lazy_Tag……

本蒟蒻：%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

因为是最小的i，所以答案具有可二分性。

所以考虑二分订单，并模拟出剩余的教室数组。

因为是区间加减，所以可以用差分维护，最后前缀和还原。

于是有了个常数巨大的姿势。

又发现差分上操作会有大量重复。

用个栈压着。

复杂度$O(nlogm)$

Code：

#include<cstdio>
#include<cstring>
#define maxn 1000010
using namespace std;
typedef long long LL;
LL r[maxn],d[maxn],s[maxn],t[maxn],S[maxn],last;
int n,m;
int judge(int x)
{
	if (x>last) //和栈顶关系
	for (int i=last+1;i<=x;i++)
	{
		S[s[i]]+=d[i];
		S[t[i]+1]-=d[i];//S维护差分信息
	}
	if (x<last)
	for (int i=x+1;i<=last;i++)
	{
		S[s[i]]-=d[i];
		S[t[i]+1]+=d[i];
	}
	int sum=0;
	last=x;
	for (int i=1;i<=n;i++)
	{
		sum+=S[i];//前缀和还原差分
		if (sum>r[i]) return 0;
	}
	return 1;
}
int main()
{
	
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%lld",&r[i]);
	for (int i=1;i<=m;i++)
		scanf("%lld%lld%lld",&d[i],&s[i],&t[i]);
	int l=1,r=m,ans=0;
	last=0;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (!judge(mid)) {ans=mid;r=mid-1;}
		else l=mid+1;
	}
	if (!ans) puts("0");
	else printf("-1\n%d",ans);
	return 0;
}

草酸君似乎还有个无敌的$O(n+m)$做法

先把订单全部用上，那么必定有很多天教室数是小于0的。那么我们可以从后往前删除订单。

然后一样是差分模拟，当这天教室数小于0，就把当前订单删除，直到这天教室数合法。

因为是删除订单，所以以前的教室一定合法。

删除订单的时候注意是维护差分数组还是前缀和的值。

Code：

#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
	LL x=0,f=1;char G;
	while(c>57||c<48){if(c=='-')f=-1;G;}
	while(c>47&&c<58)x=x*10+c-48,G;
	return x*f;
}
LL w[maxn],dt[maxn],c[maxn],l[maxn],r[maxn],cur=0;
int main()
{
	int n=read(),m=read(),M=m;
	for(int i=1;i<=n;i++)dt[i]=(w[i]=read())-w[i-1];
	for(int i=1;i<=m;i++)
		c[i]=read(),l[i]=read(),r[i]=read()+1,dt[l[i]]-=c[i],dt[r[i]]+=c[i];
	for(int i=1;i<=n;i++)
		for(cur+=dt[i];cur<0;m--)
			if(l[m]>i)dt[l[m]]+=c[m],dt[r[m]]-=c[m];
			else if(r[m]>i)cur+=c[m],dt[r[m]]-=c[m];
	if(m==M)puts("0");
	else printf("-1\n%d",m+1);
	return 0;
}