链接：https://ac.nowcoder.com/acm/contest/317/G
来源：牛客网
 

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

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

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

 

 

输入描述:

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

输出描述:

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

示例1

输入

复制

5 2 3 
5 2 1 3 4 

8 3 5
6 7 1 8 5 2 4 3

输出

 2 4
 5 8

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

 

首先，一个区间[l, r]是连续区间当且仅当
我们维护出每个数出现的位置，即;表示数x的位置，考虑每次迭带更新答案。
维护四个变量l,r,minn,maxx分别表示当前区间的左右端点，最大最小值
首先找到[,]中的每个数位置的最大最小值来找到下一轮的l,r;
接下来不断扩充当前的l,r，扩充的同时更新minn,maxx，再不断用新的minn,maxx更新l,r，直到找到一段连
续区
当找到第一个满足条件的区间即为长度最小的区间，实际上长度最小的区间的左右端点只有一种方案，
因为两段相交的连续区间的交集也是连续区

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
void chmin(int &a, int b) {a = (a < b ? a : b);}
void chmax(int &a, int b) {a = (a > b ? a : b);}
int a[maxn],pos[maxn];
int main()
{
    int N,L,R;
    N=read();L=read();R=read();
    for(int i=1;i<=N;i++)a[i]=read(),pos[a[i]]=i;
    L=pos[L],R=pos[R];
    if(L>R)swap(L,R);
    int minn=99999999,maxx=0,l=L,r=R;
    for(int i=L;i<=R;i++)chmin(minn,a[i]),chmax(maxx,a[i]);
    for(int i=minn;i<=maxx;i++)chmin(l,pos[i]),chmax(r,pos[i]);
    while(l<L||R<r)
    {
        int tmin=minn,tmax=maxx;
        while(l<L)chmin(tmin,a[--L]),chmax(tmax,a[L]);
        while(R<r)chmin(tmin,a[++R]),chmax(tmax,a[R]);
        for(int i=tmin;i<=minn;i++)chmin(l,pos[i]),chmax(r,pos[i]);
        for(int i=maxx;i<=tmax;i++)chmin(l,pos[i]),chmax(r,pos[i]);
        minn=tmin;maxx=tmax;
    }
    cout<<l<<" "<<r<<endl;
    return 0;
}