分析

这场比赛较难的一道题。我们可以根据坐标建一根线段树，然后在线段树上二分。这样就可以做到 ，而并不是题解的 。没有太大思维量，根据题意把线段树建出来，然后对于每一个节点模拟一下就好了。主要还是考察了代码能力吧。要注意是按输入顺序来考虑的，而不是坐标的从左向右。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
int mx[N],mi[N],n,B[N],h[N];
struct Node{int id,x,H;}P[N];
bool cmpx(Node a,Node b) {return a.x < b.x;}
bool cmpid(Node a,Node b) {return a.id < b.id;}
void build(int u,int l,int r) {
    if(l == r) {h[l] = mx[u] = P[l].H;mi[u] = l;return;}
    int mid = l + r >> 1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    mx[u] = max(mx[u<<1|1],mx[u<<1]);
    if(h[mi[u<<1]] <= h[mi[u<<1|1]]) mi[u] = mi[u<<1];
    else mi[u] = mi[u<<1|1];
}
void update(int u,int l,int r,int pos,int k) {
    if(l == r) {h[l] = mx[u] = k;mi[u] = l;return;}
    int mid = l + r >> 1;
    if(pos <= mid) update(u<<1,l,mid,pos,k);
    else update(u<<1|1,mid+1,r,pos,k);
    mx[u] = max(mx[u<<1|1],mx[u<<1]);
    if(h[mi[u<<1]] <= h[mi[u<<1|1]]) mi[u] = mi[u<<1];
    else mi[u] = mi[u<<1|1];
}
int askmx(int u,int l,int r,int L,int R,int h) {
    int mid = l + r >> 1;
    if(L <= l && r <= R) {
        if(l == r) return mx[u] > h ? l : 0;
        if(mx[u<<1|1] > h) return askmx(u<<1|1,mid+1,r,L,R,h);
        else if(mx[u<<1] > h) return askmx(u<<1,l,mid,L,R,h);
        else return 0;
    }
    int ans = 0;
    if(mid < R) ans = askmx(u<<1|1,mid+1,r,L,R,h);
    if(ans == 0 && L <= mid) ans = askmx(u<<1,l,mid,L,R,h);
    return ans;
}
int askmi(int u,int l,int r,int L,int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return mi[u];
    int mid = l + r >> 1;
    int posl = askmi(u<<1,l,mid,L,R);
    int posr = askmi(u<<1|1,mid+1,r,L,R);
    if(h[posl] <= h[posr]) return posl;else return posr;
}
int Id[N];
int main() {
    n = read();
    for(int i = 1;i <= n;i++) {
        P[i].id = i;B[i] = P[i].x = read();P[i].H = read();
    }
    h[0] = 0x3f3f3f3f;
    sort(B + 1,B + 1 + n);
    for(int i = 1;i <= n;i++) {P[i].x = lower_bound(B+1,B+1+n,P[i].x) - B;}
    sort(P + 1,P + 1 + n,cmpx);
    for(int i = 1;i <= n;i++) Id[P[i].id] = i;
    build(1,1,n);
    sort(P + 1,P + 1 + n,cmpid);
    for(int i = 1;i <= n;i++) {
        int pos = P[i].x,posmx = 0,posmi = 0;
        if(pos != 1) posmx = askmx(1,1,n,1,pos-1,h[P[i].x]);
        if(posmx) {
            update(1,1,n,posmx,h[P[i].x]);
        }
        posmx = 0;
        if(pos != n) {
            posmx = askmx(1,1,n,pos+1,n,h[P[i].x]);
            if(posmx == 0) posmi = askmi(1,1,n,pos+1,n);
        } 
        if(posmi) {
            update(1,1,n,posmi,h[P[i].x]);
        }
    }
    for(int i = 1;i <= n;i++) {
        printf("%d ",h[Id[i]]);
    }
    printf("\n");
    return 0;
}