自动搬运

查看原文

来自洛谷，原作者为

	i207M 这个家伙很蠢，什么也没有留下

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

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

以下是正文

今天考试正好考了这道题，然后我就因为读错题爆零了，回去钻研博客，发篇题解。

写在之前：这道题可以用图论的方法解决，具体思想是用线段树优化区间连边，然后缩scc...balabala

上面的我不会

我们把题干里描述的区间成为“好区间”。一条性质：好区间的交也是好区间。

处理这种问题，一个利器就是离线之后线段树扫描线。

设当前扫描线扫描到r，关键就是如何维护$[l,r]$是否为好的区间。

我先说方法，再说证明：

建立一棵线段树，维护最大值和最大值出现的最靠右的位置。设线段树上每个点的权值为val[i]，则初值为$val[i]=i$

从左到右扫描，设$p[v]$表示权值v出现的位置。执行下面的代码，其中upd为区间+1.

if(a[i]>1&&p[a[i]-1]<=i) upd(1,p[a[i]-1]);
if(a[i]<n&&p[a[i]+1]<=i) upd(1,p[a[i]+1]);

那么，如果$val[l]==r$，则$[l,r]$是“好区间”。

证明：

如果区间长度为2，即$val[r-1]=r$，那么显然$a[r-1]=a[r]-1 \text{ or } a[r]+1$

如果$val[l]==r$，那么$val[l]$处被++了$r-l$次。也就是说，在$[l,r]$区间内，存在$r-l$个相邻的数对。根据咕咕原理，权值区间一定是连续的。

换一种理解，如果$[l,r]$的权值区间为$[c,d]+[e,f],e-d>1$，那么d和e就不能贡献“相邻的数对”，所以$val[l]$被覆盖的次数一定$<r-l$次。

询问按L从大到小排序。

#define N 100005
#define M N*4
#define ls (x<<1)
#define rs (x<<1|1)
#define gm int mid((l+r)/2)
int n,a[N],p[N];
const int rt=1;
int mx[M],pos[M],laz[M];
il void up(int x)
{
	mx[x]=max(mx[ls],mx[rs]);
	pos[x]=mx[ls]>mx[rs]?pos[ls]:pos[rs];
}
il void down(int x)
{
	if(laz[x])
	{
		mx[x]+=laz[x];
		if(rs<M)
		{
			laz[ls]+=laz[x],laz[rs]+=laz[x];
		}
		laz[x]=0;
	}
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		mx[x]=pos[x]=l;
		return;
	}
	gm;
	build(ls,l,mid), build(rs,mid+1,r);
	up(x);
}
void upd(int x,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)
	{
		++laz[x];
		down(x);
		return;
	}
	gm; down(x);
	if(ql<=mid) upd(ls,l,mid,ql,qr);
	else down(ls);
	if(qr>mid) upd(rs,mid+1,r,ql,qr);
	else down(rs);
	up(x);
}
int al,ar;
void ask(int x,int l,int r,int ql,int qr)
{
	down(x);
	if(ql<=l&&r<=qr)
	{
		if(mx[x]>=ar)
		{
			al=pos[x],ar=mx[x];
		}
		return;
	}
	gm;
	if(ql<=mid) ask(ls,l,mid,ql,qr);
	if(qr>mid) ask(rs,mid+1,r,ql,qr);
}
pairint ans[N];
bool judge(pairint x,int r)
{
	ar=-1; ask(rt,1,n,1,x.fi);
	if(ar==r)
	{
		ans[x.se]=mp(al,ar);
		return 1;
	}
	return 0;
}
vector<pairint>g[N];
priority_queue<pairint>s;
signed main()
{
#ifdef M207
	freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
#endif
	in(n);
	for(ri i=1; i<=n; ++i) in(a[i]),p[a[i]]=i;
	int cntq; in(cntq);
	for(ri i=1,l,r; i<=cntq; ++i)
	{
		in(l),in(r);
		g[r].pb(mp(l,i));
	}
	build(rt,1,n);
	for(ri i=1; i<=n; ++i)
	{
		if(a[i]>1&&p[a[i]-1]<=i) upd(rt,1,n,1,p[a[i]-1]);
		if(a[i]<n&&p[a[i]+1]<=i) upd(rt,1,n,1,p[a[i]+1]);
		for(const pairint &v:g[i]) s.push(v);
		while(!s.empty())
		{
			if(judge(s.top(),i)) s.pop();
			else break;
		}
	}
	for(ri i=1; i<=cntq; ++i) out(ans[i].fi,' '),out(ans[i].se);
	return 0;
}