2 条题解
-
1
权值线段树,下标为数值,存的是原数组中的下标。
查询时只需要查询 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
看到有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
- 上传者