2 条题解

  • 1
    @ 2026-10-19 14:02:58

    权值线段树,下标为数值,存的是原数组中的下标。

    查询时只需要查询 min 即可。

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    struct node{
        int w;
    }tr[4000008];
    inline int lowbit(int x){
        return x&(-x);
    }
    inline void pushup(int root){
        tr[root].w=min(tr[root<<1].w,tr[root<<1|1].w);
    }
    inline void build(int root,int L,int R){
        if(L==R){
            tr[root].w=0x3f3f3f3f;
            return;
        }
        int mid=L+R>>1;
        build(root<<1,L,mid);
        build(root<<1|1,mid+1,R);
        pushup(root);
    }
    inline void update(int root,int L,int R,int c,int x){
        if(L==R&&L==c){
            tr[root].w=x;
            return;
        }
        int mid=L+R>>1;
        if(c<=mid) update(root<<1,L,mid,c,x);
        else update(root<<1|1,mid+1,R,c,x);
        pushup(root);
    }
    inline int query(int root,int L,int R,int l,int r){
        if(L>=l&&R<=r){
            return tr[root].w;
        }
        int mid=L+R>>1,ans=0x3f3f3f3f;
        if(l<=mid) ans=min(ans,query(root<<1,L,mid,l,r));
        if(r>=mid+1) ans=min(ans,query(root<<1|1,mid+1,R,l,r));
        return ans;
    }
    signed main(){
        cin.tie(0);
        ios::sync_with_stdio(false);
        int N=1e6+1;
        int n;
        cin>>n;
        int ANS[n+5]={0},a[n+5];
        for(int i=1; i<=n; i++) cin>>a[i];
        build(1,1,N);
        for(int i=n; i>=1; i--){
            ANS[i]=query(1,1,N,a[i]+1,N);
            update(1,1,N,a[i],i);
        }
        for(int i=1; i<=n; i++) cout<<(ANS[i]==0x3f3f3f3f?0:ANS[i])<<"\n";
        return 0;
    }
    

    信息

    ID
    911
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    4
    已通过
    4
    上传者