CF1793C Dora and Search

题意

给定一个长度为 \(n\) 的排列 \(a\) ，问是否存在正整数 \(l,r\) 使得 \(a_l,a_r\) 均不为 \(a_{l...r}\) 中的最大值或最小值。

思路

很明显的双指针，~~虽然我最开始的思路是二分~~

预处理当前序列的最大值和最小值，并且一旦两段的\(l,r\)中有一个是最大或最小值，那么就移动，并且更新

那该怎么更新呢？最大值如果访问过了，那么新的最大值就是当前的减一

反之，最小值就是当前的加一

还有一点需要注意，就是\(l-r+1\) （即区间长度）一定大于\(2\)，否则就无法构造了

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int a[Maxn],f[Maxn];
int n,l,r;
int maxn,minn;
void run()
{
    cin>>n;l=1,r=n;maxn=-1,minn=1e9+10;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        maxn=max(maxn,a[i]);
        minn=min(minn,a[i]);
    }
    while(l+2<=r)
    {
        int flag=1;
        if(a[l]==maxn) maxn=a[l]-1,l++,flag=0;
        else if(a[r]==maxn) maxn=a[r]-1,r--,flag=0;
        if(a[l]==minn) minn=a[l]+1,l++,flag=0;
        else if(a[r]==minn) minn=a[r]+1,r--,flag=0;
        if(flag) break;
    }
    if(l+2<=r) cout<<l<<" "<<r<<endl;
    else cout<<-1<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--) run();
}