会当凌绝顶，一览众山小

题目（划重点）

  • 登山顺序不一定从左到右，是按照给出山峰的顺序
  • 找到左边第一个大于当前山峰的山峰的坐标，修改他
  • 如果右边没有大于当前山峰的，找到离当前山峰最近的最矮山峰，修改它

分析

  • 线段树实现
  • 首先，由于下标范围过大，离散一波。然后建一棵线段树，存储最大值和最小值。
  • 左边：假设当前是第i座山，映射过去的位置是pos(离散化)，二分[1,pos]区间，找到最近的一个大于当前高度的山
  • 右边：同理。假设映射的位置是pos,先求出区间[pos+1,n]的最大值判断需不需要修改。若是需要，则二分[pos+1,n]
    区间，找到最近的一个最小值

代码

#include<bits/stdc++.h>
#define ls now<<1
#define rs now<<1|1
using namespace std;
const int N=2e5+10;

int n,cnt;
int h[N],ma[N<<2],mi[N<<2],b[N];

struct nkl{int x,y;}s[N];

inline void upd(int now)
{
    ma[now]=max(ma[ls],ma[rs]);
    mi[now]=min(mi[ls],mi[rs]);
}

inline void build(int now,int l,int r)
{
    if(l==r)
    {
        mi[now]=ma[now]=h[l];
        return ;
    }

    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);

    upd(now);
}

inline int askmx(int now,int l,int r,int x,int y)
{
    if(l>=x&&r<=y) return ma[now];

    int mid=(l+r)>>1,ret=-1e9;
    if(x<=mid) ret=askmx(ls,l,mid,x,y);
    if(mid<y) ret=max(ret,askmx(rs,mid+1,r,x,y));

    return ret;
}

inline int askmi(int now,int l,int r,int x,int y)
{
    if(l>=x&&r<=y) return mi[now];

    int mid=(l+r)>>1,ret=1e9;
    if(x<=mid) ret=askmi(ls,l,mid,x,y);
    if(mid<y) ret=min(ret,askmi(rs,mid+1,r,x,y));

    return ret;
}

inline void ud(int now,int l,int r,int x,int z)
{
    if(l==r)
    {
        ma[now]=mi[now]=z;
        return ;
    }

    int mid=(l+r)>>1;
    if(x<=mid) ud(ls,l,mid,x,z);
    else ud(rs,mid+1,r,x,z);

    upd(now);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&s[i].x,&s[i].y);
        b[i]=s[i].x;
    }sort(b+1,b+n+1);

    for (int i=1;i<=n;i++)
    {
        int p=lower_bound(b+1,b+n+1,s[i].x)-b;
        h[p]=s[i].y;
    }build(1,1,n);

    for (int i=1;i<=n;i++)
    {
        int pos=lower_bound(b+1,b+n+1,s[i].x)-b;
        //位置
        //第一步:找到左边第一个大于当前高度的
        int xx=askmx(1,1,n,1,pos);
        if(xx>h[pos])
        {
            int l=1,r=pos,ans=0;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                xx=askmx(1,1,n,mid,pos);
                if(xx>h[pos]) ans=mid,l=mid+1;
                else r=mid-1;
            }
            h[ans]=h[pos];ud(1,1,n,ans,h[pos]);
        }

        if(pos==n) continue;

        int yy=askmx(1,1,n,pos+1,n);
        if(yy<=h[pos])
        {
            int kp=askmi(1,1,n,pos+1,n);//最小的那个
            int l=pos+1,r=n,ans=0;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                yy=askmi(1,1,n,pos+1,mid);
                if(yy==kp) ans=mid,r=mid-1;
                else l=mid+1;
            }
            h[ans]=h[pos];ud(1,1,n,ans,h[pos]);
        }
    }

    for (int i=1;i<=n;i++)
    {
        int x=lower_bound(b+1,b+n+1,s[i].x)-b;
        printf("%d ",h[x]);
    }

    return 0;
}