题解 | #单调栈结构(进阶)#

#include <iostream>
#include <vector>

const int MAXN = 1000001;
int arr[MAXN];
int stack[MAXN];
int ans[MAXN][2];
int n, r;

void compute() {
    r = 0;
    int cur;
    // Traverse the array
    for (int i = 0; i < n; i++) {
        while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
            cur = stack[--r];
            // Left and right less value
            ans[cur][0] = r > 0 ? stack[r - 1] : -1;
            ans[cur][1] = i;
        }
        stack[r++] = i;
    }
    // Final adjustment phase for remaining elements
    while (r > 0) {
        cur = stack[--r];
        ans[cur][0] = r > 0 ? stack[r - 1] : -1;
        ans[cur][1] = -1;
    }
    // Right-hand side adjustment
    for (int i = n - 2; i >= 0; i--) {
        if (ans[i][1] != -1 && arr[ans[i][1]] == arr[i]) {
            ans[i][1] = ans[ans[i][1]][1];
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    while (std::cin >> n) {
        for (int i = 0; i < n; i++) {
            std::cin >> arr[i];
        }
        compute();
        for (int i = 0; i < n; i++) {
            std::cout << ans[i][0] << " " << ans[i][1] << "\n";
        }
    }
    return 0;
}