小a的排列（牛客）

题目

题意：

　　一个长度为n的排列。输入n个数 a[ i ]，a[ i ] ∈ [1,n]，要求找到长度最小的区间 [ l , r ]，满足区间[ l , r ]内的数是连续的，且同时包含 数 x 和 数 y 。

思路：

　　容易得： 要想得到这个区间，这个区间内必须满足 “最大值 - 最小值 == r - l ” 。我们维护出每个数出现的位置，即p[x]表示数x的位置，考虑每次迭带更新答案。维护四个变量 分别表示当前区间的左右端点，最大最小值。

　　首先找到[p[x], p[y]]中的每个数位置的最大最小值来找到下一轮的 l, r，接下来不断扩充当前的l, r，扩充的同时更新最大值和最小值，再不断用新的最大值最小值更新 l, r，直到找到一段连续区间。

#include<iostream>

#include<cstdio>

#include <cctype>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<string>

#include<cmath>

#include<set>

#include<vector>

#include<stack>

#include<queue>

#include<map>

using namespace std;

#define ll long long

#define mem(a,x) memset(a,x,sizeof(a))

#define se second

#define fi first

const ll mod=1e9+;

const int INF= 0x3f3f3f3f;

const int N=2e5+;

int a[N],p[N];

int main()

{

    int n,x,y;

    cin>>n>>x>>y;

    int l,r,maxn=-,minn=INF;

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        p[a[i]]=i;

    }

    l=p[x]; r=p[y];

    if(l>r) swap(l,r);

    for(int i=l;i<=r;i++)

    {

        maxn=max(maxn,a[i]);

        minn=min(minn,a[i]);

    }

    int L=INF,R=-;

    for(int i=minn;i<=maxn;i++)

    {

        L=min(L,p[i]);

        R=max(R,p[i]);

    }

    int tmn=minn,tmx=maxn;

    if(tmx-tmn==R-L)

    {

           cout<<L<<' '<<R<<endl;

           return ;

    }

    while(tmx-tmn!=r-l)

    {

        while(L < l) tmn=min(tmn, a[--l]), tmx=max(tmx, a[l]);

        while(r < R) tmn=min(tmn, a[++r]), tmx=max(tmx, a[r]);

        for(int i = tmn; i <= minn; i++) L=min(L, p[i]), R=max(R, p[i]);

        for(int i = maxn; i <= tmx; i++) L=min(L, p[i]), R=max(R, p[i]);

        maxn=tmx;

        minn=tmn;

    }

    cout<<l<<' '<<r<<endl;

}