自动搬运

查看原文

来自洛谷，原作者为

	ykzzldz 做自己，别管别人

搬运于2025-08-24 23:10:21，当前版本为作者最后更新于2025-02-25 10:35:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题还是比较有趣的。

首先分析一下题目，题目中给出了一个比较奇怪的限制，区间长度不同。一般来说，这种限制要么是为了保证题目有解，要么是保证复杂度。这题中显然不是前者，但具体是如何保证复杂度的，我们先继续思考。

另外，发现除了 $a_i$ 之外，其他的值域都是 $10^{18}$ 级别，说明最后的复杂度大概率与 $a_i$ 有关。

题目给出的条件其实是说对于给定的 $m$ 个区间，将每个区间向左平移 $a_i$ 个单位，被区间覆盖的位置是被 ban 掉的，求没被 ban 掉的数的个数。由于 $a_i$ 非常小，我们对这个题目有一个大体的感受，那就是区间之间会有许多交集。

具体分析一下，若有一个区间 $[l,r]$，分别有两个平移的距离 $a_i<a_j$，最后形成的区间 $[l-a_i,r-a_i]$ 和 $[l-a_j,r-a_j]$ 有交的条件为 $l-a_j\le r-a_i$，即 $a_i-a_j\le r-l$。考虑将每 $r-l$ 分为一段，一段中的 $a_i$ 都是可以合并的，也就是说，每段会合并出一个区间。这样，形成的区间个数是 $\frac{a_i}{r-l}$ 的。在复杂度的分析中，默认 $O(a_i)=O(n)$。由于区间长度不同，根据调和级数，区间的个数是 $O(n\log n)$ 的。这也印证了我们一开始的关于区间长度不同保证复杂度的猜想。

令 $S=n\log n$，这样总的时间复杂度为 $O(S\log S)$，可能无法通过这题。但是，我们只要对每个区间处理的时候先按上面的步骤合并一次，再将合并出的区间合并第二次，就会大大减少区间的个数。经过实测，两次合并后的区间个数小于 $10^6$ 个，可以非常轻松地通过。不过我也不太清楚这里的复杂度是否有所改变，因为这里合并后的区间个数居然是 $O(n)$ 级别的，希望大家可以一起分析一下。下面给出代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5,M=1e6,inf=2e18;
struct node{
	int l,r;
}b[M],c[N];
bool cmp(node a,node b){
	return a.l<b.l;
}
int n,m,v,a,l,r,L[N+10],R[N+10],cnt;
signed main(){
	scanf("%lld%lld%lld",&n,&m,&v);
	memset(R,127,sizeof R);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a);
		L[a]=R[a]=a;
	}
	for(int i=1;i<=N;i++){
		L[i]=max(L[i],L[i-1]);
	}
	for(int i=N;i>=1;i--){
		R[i]=min(R[i],R[i+1]);
	}
	c[0]={inf,inf};
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&l,&r);
		int len=r-l,cnt0=0;
		for(int ll=1;ll<=N;ll+=len+1){
			int rr=ll+len;
			if(rr>N)rr=N;
			int a1=R[ll],a2=L[rr];
			if(a1>rr||a2<ll)continue;
			int LL=l-a2,RR=r-a1;
			if(RR<1)continue;
			if(LL<1)LL=1;
			if(LL>v)continue;
			if(RR>v)RR=v;
			c[++cnt0]={LL,RR};
		}
		int lll=c[cnt0].l,rrr=c[cnt0].r;
		for(int j=cnt0-1;j>=0;j--){
			if(c[j].r<=rrr)continue;
			if(c[j].l<=rrr)rrr=c[j].r;
			else{
				b[++cnt]={lll,rrr};
				lll=c[j].l,rrr=c[j].r;
			}
		}
	}
	sort(b+1,b+1+cnt,cmp);
	int ans=v,mx=0;
	for(int i=1;i<=cnt;i++){
		if(b[i].r<=mx)continue;
		if(b[i].l<=mx)ans-=(b[i].r-mx);
		else ans-=(b[i].r-b[i].l+1);
		mx=b[i].r;
	}
	cout<<ans;
	return 0;
}