https://ac.nowcoder.com/acm/contest/317/G

C++版本一

std

题解：模拟，思维

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
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 N, L, R, a[MAXN], pos[MAXN];
int main() {
//	freopen("a.in", "r", stdin);
    //freopen("a10.out", "w", stdout);
    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 mx = -1, mn = INF, l = L, r = R;
    for(int i = L; i <= R; i++) chmin(mn, a[i]), chmax(mx, a[i]);
    for(int i = mn; i <= mx; i++) chmin(l, pos[i]), chmax(r, pos[i]);
    while(l < L || R < r){
        int tmn = mn, tmx = mx;
        while(l < L) chmin(tmn, a[--L]), chmax(tmx, a[L]);
        while(R < r) chmin(tmn, a[++R]), chmax(tmx, a[R]);
        for(int i = tmn; i <= mn; i++) chmin(l, pos[i]), chmax(r, pos[i]);
        for(int i = mx; i <= tmx; i++) chmin(l, pos[i]), chmax(r, pos[i]);
        mn = tmn; mx = tmx;
    }
    cout << l << ' ' << r;
    return 0;
}