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;
    }
    
    • 0
      @ 2026-11-3 11:19:45

      看到有dalao用神秘的权值线段树,我畏惧了。

      实际上这就是一个单调栈的板子题,我们如果发现栈顶的元素严格小于当前的元素,那么我们记录答案即可。

      Code:

      #include<bits/stdc++.h>
      #define int long long
      #define I_love_ch ios::sync_with_stdio(0)
      #define China cin.tie(0)
      #define France cout.tie(0)
      #define ch_France return 0
      #define Nyacode main
      using namespace std;
      int n,a[100010],st[100010],top,ans[100010];
      signed Nyacode(){
      	I_love_ch;
      	China;
      	France;
      	cin>>n;
      	for(int i=1;i<=n;i++){
      		cin>>a[i];
      	}
      	for(int i=1;i<=n;i++){
      		while(top&&a[i]>a[st[top]]){
      			ans[st[top]]=i;
      			top--;
      		}
      		st[++top]=i;
      	}
      	for(int i=1;i<=n;i++){
      		cout<<ans[i]<<"\n";
      	}
      	ch_France;
      }
      
      • 1

      信息

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