牛客小白月赛28 E 会当临绝顶，一览众山小

题目可以转化成
1） 找某个坐标左边第一个比他大的数。
2） 找某个坐标右边最小的数。

这两个操作分别可以用两颗线段树维护。

1）中维护区间max，如果右区间最大值比要查询的值大，则递归右区间，否则递归左区间。
2）中维护区间min，如果据区间最小值比右区间最小值小，递归左区间，否则递归右区间。

复杂度O(nlogn)

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define lson rt * 2
#define rson rt * 2 + 1
#define MP make_pair

const int N = 4e5 + 100;

namespace Ma {
    int tree[N * 4];

    void insert(int id, int x, int l, int r, int rt) {
        if (l == r) {
            tree[rt] = x;
            return;
        }
        int m = (l + r) / 2;
        if (id <= m) insert(id, x, l, m, lson);
        else insert(id, x, m + 1, r, rson);
        tree[rt] = max(tree[lson], tree[rson]);
    }

    int query(int ql, int qr, int x, int l, int r, int rt) {
        if (tree[rt] <= x) return 0;
        if (l == r) return l;
        int m = (l + r) / 2;
        if (qr <= m) return query(ql, qr, x, l, m, lson);
        else {
            int t = query(m + 1, qr, x, m + 1, r, rson);
            if (t) return t;
            return query(ql, m, x, l, m, lson);
        }
    }

    int query2(int ql, int qr, int l, int r, int rt) {
        if (ql == l && qr == r) return tree[rt];
        int m = (l + r) / 2;
        if (qr <= m) return query2(ql, qr, l, m, lson);
        else if (m < ql) return query2(ql, qr, m + 1, r, rson);
        return max(query2(ql, m, l, m, lson), query2(m + 1, qr, m + 1, r, rson));
    }
}

int n;
int h[N], xx[N], rev[N];

namespace Mi {
    int tree[N * 4];

    void insert(int id, int x, int l, int r, int rt) {
        if (l == r) {
            tree[rt] = x;
            return;
        }
        int m = (l + r) / 2;
        if (id <= m) insert(id, x, l, m, lson);
        else insert(id, x, m + 1, r, rson);
        tree[rt] = min(tree[lson], tree[rson]);
    }

    int query(int ql, int qr, int l, int r, int rt) {
        if (l == r) return l;
        int m = (l + r) / 2;
        if (m < ql) return query(ql, qr, m + 1, r, rson);
        else {
            int t = 0;
            if (tree[lson] <= tree[rson]) t = query(ql, m, l, m, lson);
            if (t && h[rev[t]] <= tree[rson]) return t;
            return query(m + 1, qr, m + 1, r, rson);
        }
    }
}

int tp, has[N], ha[N];

void change(int i, int x) {
    h[i] = x;
    Ma::insert(xx[i], h[i], 1, n, 1);
    Mi::insert(xx[i], h[i], 1, n, 1);
}


int main() {
    //freopen("0.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", xx + i, h + i);
        has[i] = h[i];
        ha[i] = xx[i];
    }
    sort(has + 1, has + n + 1);
    tp = unique(has + 1, has + n + 1) - has;
    for (int i = 1; i <= n; i++) h[i] = lower_bound(has + 1, has + tp, h[i]) - has;
    sort(ha + 1, ha + n + 1);
    for (int i = 1; i <= n; i++) xx[i] = lower_bound(ha + 1, ha + n + 1, xx[i]) - ha, rev[xx[i]] = i;
    for (int i = 1; i <= n; i++) change(i, h[i]);
    for (int i = 1; i <= n; i++) {
        int t = Ma::query(1, xx[i], h[i], 1, n, 1);
        if (t) change(rev[t], h[i]);
        if (xx[i] + 1 <= n && Ma::query2(xx[i] + 1, n, 1, n, 1) <= h[i]) {
            t = Mi::query(xx[i] + 1, n, 1, n, 1);
            change(rev[t], h[i]);
        }
    }
    for (int i = 1; i <= n; i++) printf("%d%c", has[h[i]], i == n ? '\n' : ' ');
    return 0;
}