2 条题解
-
0
看到有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
- 上传者