2 条题解

  • 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;
    }
    

    信息

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