自动搬运

查看原文

来自洛谷，原作者为

	xzx34 但就是因为你能这样思考，才意味着你拥有着，能让你越来越强大的力量

搬运于2025-08-24 22:15:39，当前版本为作者最后更新于2020-03-27 20:18:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此题的关键在于对“数段”性质的使用。 考虑“数段”的性质：

1 起点为该数段最小的数字。

2 终点为该数段最大的数字且与起点不是同一个数字。

3 且介于这两个数字之间所有的整数都出现在这个数段中。

考虑“障碍段”的性质：

4 框段中并不包含更短的框段，则称之为障碍段

基本思路开个mp数组记录每一个数对应的位置，从后往前枚举区间起点，利用mp数组从起点开始跳。

如果跳到了一个点满足：

1 位置大于在这次过程中，之前跳到的所有点的位置

2 这个点的位置-起跳点的位置==这个点的数-起跳点的数

这就是个合法的数段。

我们考虑一下这个过程的复杂度，理论最劣可达到M^2;

考虑如何运用数段的性质优化这一过程。

如果我跳到了一个点在我的起跳点之前，考虑性质1，直接退出，必定不合法。

我们记录目前找到的区间的右端点位置，保留最小的那条记录R。考虑性质4，如果我跳的点的位置大于R，即使我这个区间满足性质123，也不能计入答案，故舍弃。

尽管如此，这个算法的复杂度还是没有保证，但实际上进行如此优化后速度很快，是目前的最优解~~（毕竟交的早）~~。

代码如下：

#include <bits/stdc++.h>
#define re register int 
#define il inline
#define ll long long
using namespace std;
const int inf=1e9;
il int read(){
	char c=getchar();int z=0,f=1;
	while(c!='-'&&(c>'9'||c<'0')) c=getchar();
	if(c=='-') f=-1,c=getchar();
	while(c>='0'&&c<='9') z=(z<<1)+(z<<3)+c-'0',c=getchar();
	return z*f;
}
int R,n;
int mp[1100002],a[1100002];
int ans;
struct ANS{
	int x,y;
}q[1100002];
il void dfs(int l,int now,int r,int sum){
	if(r>=R) return ;
	if(mp[now]<l) return ;
	if(r==mp[now]&&sum>1&&sum==r-l+1) {
		q[++ans].x=l,q[ans].y=r,R=min(R,r);
		return ;
	}
	dfs(l,now+1,max(r,mp[now+1]),sum+1);
}
int main (){
	//Fuyuki是我们的红太阳 
	freopen("empodia.in","r",stdin);
	freopen("empodia.out","w",stdout);
	n=read();R=n+1;
	for(re i=1;i<=n;i++) a[i]=read(),mp[a[i]]=i;
	for(re i=n-2;i>=1;i--) 
		dfs(i,a[i],i,1);
	cout<<ans<<'\n';
	for(re i=ans;i>=1;i--)
		cout<<q[i].x<<' '<<q[i].y<<'\n';
	return 0;
}