自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 22:19:56，当前版本为作者最后更新于2020-12-22 15:00:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我们对于询问做莫队。一种简单的错误想法是把 $2n$ 个端点离散化之后拿来莫队，但是假如 $l<L$，$r>R$，则询问 $[L,R]$ 是算不到 $[l,r]$ 这个区间的贡献的。也就是，这样无法处理“包含”的情况。

为了能够处理这种情况，我们考虑回滚莫队。把左端点放在所属块上，考虑右端点的位置分类讨论。

• 两端点在同一块（设为 $i$）：
  • 把包含这一块的区间先加到某个数据结构里，然后不管他们（这些一定有贡献）
  • 剩下的可能产生贡献区间（也就是至少有一端在块内的区间）只有 $O(\sqrt n)$ 个，扫一遍，加到某个数据结构里，更新答案就行
  • 这部分复杂度 $O(T(n)q\sqrt n)$
• 否则（左端点属于 $i$，右端点所属 $>i$）从左往右扫左端点在该块的询问的右端点
  • 把横跨了 $i,i+1$ 两块的区间先加到某个数据结构里，然后不管他们（这些一定有贡献）
  • 剩下的区间不可能包含询问区间了，做普通的回滚莫队即可
  • 这部分复杂度 $O(T(n)q\sqrt n)$

以上的“某个数据结构”需要在 $T(n)$ 复杂度内支持：

• 加入一个元素
• 询问最大的元素连续段
• 撤销最后几次操作（回滚）

用线段树实现是 $O(\log n)$ 的，其实直接用两个数组 $l,r$ 就可以 $O(1)$ 实现。具体看代码吧：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,Q,bel[200005],ass[200005],tmp[200005],st[1005],ed[1005];
struct Seg{
	int l,r,id;
}t[200005];
struct Thing{
	int x,id;
}a[200005];
struct Query{
	int l,r,id;
};
bool operator <(const Thing i,const Thing j){
	return i.x!=j.x?i.x<j.x:i.id<j.id;
}
vector<Query> q[1005];
int l[200005],r[200005],ans=0,top=0;
struct Oper{
	int c,x,ax,ans;
}S[3000005];
inline void Add(int x){
	if(l[x]||r[x])return ;
	if(!l[x-1]&&!r[x+1])S[++top]={0,x,l[x],ans},S[++top]={1,x,r[x],ans},l[x]=r[x]=x,ans=max(ans,1);
	else if(!l[x-1])S[++top]={0,r[x+1],l[r[x+1]],ans},S[++top]={1,x,r[x],ans},l[r[x+1]]=x,r[x]=r[x+1],ans=max(ans,r[x]-x+1);
	else if(!r[x+1])S[++top]={1,l[x-1],r[l[x-1]],ans},S[++top]={0,x,l[x],ans},r[l[x-1]]=x,l[x]=l[x-1],ans=max(ans,x-l[x]+1);
	else S[++top]={1,l[x-1],r[l[x-1]],ans},S[++top]={0,r[x+1],l[r[x+1]],ans},S[++top]={0,x,l[x],ans},
		 l[r[x+1]]=l[x-1],r[l[x-1]]=r[x+1],l[x]=x,ans=max(ans,r[x+1]-l[x-1]+1);
}
void Rollback(int t){
	while(top>t){
		if(!S[top].c)l[S[top].x]=S[top].ax;
		else r[S[top].x]=S[top].ax;
		ans=S[top].ans,top--;
	}
}
void Solve(int id){
	Rollback(0);
	for(int i=1;i<=n;i++)if(t[i].l<st[id]&&t[i].r>ed[id])Add(t[i].id);
	sort(q[id].begin(),q[id].end(),[](Query i,Query j){return i.r<j.r;});
	int tp=top,cur=ed[id];
	for(Query i:q[id]){
		if(i.r>ed[id])continue;
		for(int j=st[id];j<=ed[id];j++)if(i.l<=t[a[j].id].r&&t[a[j].id].l<=i.r)Add(a[j].id);
		ass[i.id]=ans,Rollback(tp);
	}
	Rollback(0);
	for(int i=1;i<=n;i++)if(t[i].l<=ed[id]&&t[i].r>ed[id])Add(t[i].id);
	for(Query i:q[id]){
		if(i.r<=ed[id])continue;
		while(cur<i.r)Add(a[++cur].id);
		tp=top;
		for(int j=ed[id];j>=i.l;j--)Add(a[j].id);
		ass[i.id]=ans,Rollback(tp);
	}
}
int main() {
	scanf("%d%d",&n,&Q);
	for(int i=1,l,r;i<=n;i++)scanf("%d%d",&l,&r),a[i]={l,i},a[i+n]={r,i},t[i]={l,r,i};
	sort(a+1,a+2*n+1);
	for(int i=1;i<=n;i++){
		t[i].l=lower_bound(a+1,a+2*n+1,(Thing){t[i].l,0})-a;
		t[i].r=upper_bound(a+1,a+2*n+1,(Thing){t[i].r,1<<30})-a-1;
	}
	int SQ=sqrt(2*n);
	for(int i=2*n;i>=1;i--)bel[i]=i/SQ+1,st[bel[i]]=i;
	for(int i=1;i<=2*n;i++)ed[bel[i]]=i;
	for(int i=1,l,r;i<=Q;i++){
		scanf("%d%d",&l,&r);
		l=lower_bound(a+1,a+2*n+1,(Thing){l,0})-a;
		r=upper_bound(a+1,a+2*n+1,(Thing){r,1<<30})-a-1;
		q[bel[l]].push_back((Query){l,r,i});
	}
	for(int i=1;i<=bel[2*n];i++)if(q[i].size())Solve(i);
	for(int i=1;i<=Q;i++)printf("%d\n",ass[i]);
	return 0;
}