E 会当凌绝顶，一览众山小

题目地址：

https://ac.nowcoder.com/acm/contest/7412/E

基本思路：

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = (int)2e5 + 10;

#define ls (index << 1)
#define rs (index << 1 | 1)

struct SegmentTree {

    struct Node {
        int l, r, sum, mn, mx, id;
    }tr[maxn * 4];

    inline void push_up(int index) { // 带储存区间最小值对应下标的push_up;
      tr[index].sum = tr[ls].sum + tr[rs].sum;
      tr[index].mx = max(tr[ls].mx, tr[rs].mx);
      if (tr[ls].mn <= tr[rs].mn) {
        tr[index].mn = tr[ls].mn;
        tr[index].id = tr[ls].id;
      } else {
        tr[index].mn = tr[rs].mn;
        tr[index].id = tr[rs].id;
      }
    }

    void build(int index, int l, int r, int *a) { // 建树;
      tr[index].l = l, tr[index].r = r;
      if (l == r) {
        tr[index].id = l;
        tr[index].sum = tr[index].mn = tr[index].mx = a[l];
        return;
      }
      int mid = (l + r) >> 1;
      build(ls, l, mid, a);
      build(rs, mid + 1, r, a);
      push_up(index);
    }

    void update(int index, int val, int x) { // 单点修改;
      if (tr[index].l == tr[index].r) {
        tr[index].sum = val;
        tr[index].mn = val;
        tr[index].mx = val;
        return;
      }
      int mid = (tr[index].l + tr[index].r) >> 1;
      if (x <= mid) update(ls, val, x);
      else update(rs, val, x);
      push_up(index);
    }

    int ask(int index, int x) { // 单点查询;
      if (tr[index].l == tr[index].r) {
        return tr[index].mn;
      }
      int mid = (tr[index].l + tr[index].r) >> 1;
      if (x <= mid) return ask(ls, x);
      else return ask(rs, x);
    }

    pii query_mn(int index, int l, int r) { // 查询区间最小值和它对应下标;
      if (tr[index].l >= l && tr[index].r <= r) {
        return mp(tr[index].mn, tr[index].id);
      }
      int mid = (tr[index].l + tr[index].r) >> 1;
      if (r <= mid) return query_mn(ls, l, r);
      else if (l > mid) return query_mn(rs, l, r);
      else {
        pii r1 = query_mn(ls, l, mid), r2 = query_mn(rs, mid + 1, r);
        return r1.first <= r2.first ? r1 : r2;
      }
    }

    int query_mx(int index, int l, int r) { // 查询区间最大值;
      if (tr[index].l >= l && tr[index].r <= r) {
        return tr[index].mx;
      }
      int mid = (tr[index].l + tr[index].r) >> 1;
      if (r <= mid) return query_mx(ls, l, r);
      else if (l > mid) return query_mx(rs, l, r);
      else return max(query_mx(ls, l, mid), query_mx(rs, mid + 1, r));
    }

    int query_pos(int index, int l, int r, int val) { // 查询区间最后一个大于val的数;
      if (tr[index].l == tr[index].r) {
        if (tr[index].mx > val) return tr[index].l;
        else return -1;
      }
      if (tr[index].l >= l && tr[index].r <= r) {
        if (tr[index].mx <= val) return -1;
      }
      int mid = (tr[index].l + tr[index].r) >> 1;
      if (r <= mid) return query_pos(ls, l, r, val);
      else if (l > mid) return query_pos(rs, l, r, val);
      // 如果是查询区间第一个大于val的数,就先往左边找;
      int tmp = query_pos(rs, mid + 1, r, val);
      if (tmp != -1) return tmp;
      else return query_pos(ls, l, mid, val);
    }

}smt;

int n,a[maxn];
struct Node{
    int x,h,pos;
    bool operator < (const Node &no) const{
      return x < no.x;
    }
}m[maxn];
int mm[maxn],ans[maxn];
signed main() {
  IO;
  cin >> n;
  rep(i, 1, n) {
    m[i].pos = i;
    cin >> m[i].x >> m[i].h;
  }
  sort(m + 1, m + 1 + n);
  rep(i, 1, n) a[i] = m[i].h, mm[m[i].pos] = i;
  smt.build(1, 1, n, a);
  rep(i, 1, n) {
    int hig = smt.ask(1, mm[i]);
    if (mm[i] != 1) {
      int pos1 = smt.query_pos(1, 1, mm[i] - 1, hig);
      if (pos1 != -1) smt.update(1, hig, pos1);
    }
    if (mm[i] != n) {
      int mx = smt.query_mx(1, mm[i] + 1, n);
      if (mx <= hig) {
        int pos2 = smt.query_mn(1, mm[i] + 1, n).second;
        smt.update(1, hig, pos2);
      }
    }
  }
  rep(i, 1, n) ans[m[i].pos] = smt.ask(1, i);
  rep(i, 1, n) cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}