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; }
信息
- ID
- 911
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 4
- 已通过
- 4
- 上传者