题干：
 

小a有一个长度为nn的排列。定义一段区间是"萌"的，当且仅当把区间中各个数排序后相邻元素的差为11
现在他想知道包含数x,yx,y的长度最小的"萌"区间的左右端点

也就是说，我们需要找到长度最小的区间[l,r][l,r]，满足区间[l,r][l,r]是"萌"的，且同时包含数xx和数yy

如果有多个合法的区间，输出左端点最靠左的方案。

 

 

输入描述:

第一行三个整数N,x,yN,x,y，分别表示序列长度，询问的两个数
第二行有nn个整数表示序列内的元素，保证输入为一个排列

输出描述:

输出两个整数，表示长度最小"萌"区间的左右端点

示例1

输入

复制

5 2 3
5 2 1 3 4

输出

复制

2 4

说明

区间[2,4]={2,1,3}[2,4]={2,1,3}包含了2,32,3且为“萌”区间，可以证明没有比这更优的方案

示例2

输入

复制

8 3 5
6 7 1 8 5 2 4 3

输出

复制

5 8

备注:

保证2⩽n⩽105,1⩽x,y⩽n

 

解题报告：

    这题首先可以证明合法的区间是唯一的，并不存在题中说的多个合法区间。然后某个区间是我们需要的 当且仅当  这个区间的长度 == 这段区间内最大值和最小值的差，也就是maxx -  minn == r - l。如果不满足，那就要将区间往外扩张，扩张到哪呢？当然是这些数中出现的最左端的和最右端的。同时可以证明这样循环最终一定有界（也就是一定是收敛的），因为最差情况就是扩展到整个区间，一定满足条件呗。这样一步步模拟最终得出答案。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 6;
const int INF = 0x3f3f3f3f;
int a[MAX],pos[MAX];
int main() {
	int n,x,y;
	cin>>n>>x>>y;
	for(int i = 1; i<=n; i++) {
		scanf("%d",a+i);
		pos[a[i]] = i;
	}
	int l = pos[x],r = pos[y];
	int maxx = -INF,minn = INF;
	if(l>r) swap(l,r);
	for(int i = l; i<=r; i++) minn = min(minn,a[i]),maxx = max(maxx,a[i]);
	while(r-l != maxx - minn) {
		for(int i = l; i<=r; i++) minn = min(minn,a[i]),maxx = max(maxx,a[i]);
		for(int i = minn; i<=maxx; i++) l = min(l,pos[i]),r = max(r,pos[i]);	
	}
	printf("%d %d\n",l,r);
	return 0 ;
}