1 条题解
-
2
#include<bits/stdc++.h> using namespace std; const int N = 100005; int rt,tot,fa[N],ch[N][2],val[N],cnt[N],sz[N]; struct Splay { void maintain(int x){ sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x]; } bool get(int x){ return x==ch[fa[x]][1]; } void clear(int x){ ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0; } void rotate(int x){ int y=fa[x],z=fa[y],chk=get(x); ch[y][chk]=ch[x][chk^1]; if(ch[x][chk^1])fa[ch[x][chk^1]]=y; ch[x][chk^1]=y; fa[y]=x; fa[x]=z; if(z)ch[z][y==ch[z][1]]=x; maintain(y); maintain(x); } void splay(int x){ for (int f=fa[x];f=fa[x],f;rotate(x)){ if(fa[f])rotate(get(x)==get(f)?f:x); } rt=x; } void ins(int k){ if(!rt){ val[++tot]=k; cnt[tot]++; rt=tot; maintain(rt); return; } int cur=rt,f=0; while(1){ if(val[cur]==k){ cnt[cur]++; maintain(cur); maintain(f); splay(cur); break; } f=cur; cur=ch[cur][val[cur]<k]; if(!cur){ val[++tot]=k; cnt[tot]++; fa[tot]=f; ch[f][val[f]<k]=tot; maintain(tot); maintain(f); splay(tot); break; } } } int rk(int k){ int res=0,cur=rt; while(1){ if(k<val[cur]){ cur = ch[cur][0]; } else{ res+=sz[ch[cur][0]]; if(k==val[cur]){ splay(cur); return res + 1; } res+=cnt[cur]; cur=ch[cur][1]; } } } int kth(int k){ int cur=rt; while(1){ if(ch[cur][0]&&k<=sz[ch[cur][0]]){ cur=ch[cur][0]; } else{ k-=cnt[cur]+sz[ch[cur][0]]; if(k<=0){ splay(cur); return val[cur]; } cur = ch[cur][1]; } } } int pre(){ int cur=ch[rt][0]; if(!cur)return cur; while(ch[cur][1])cur=ch[cur][1]; splay(cur); return cur; } int nxt(){ int cur=ch[rt][1]; if(!cur)return cur; while(ch[cur][0])cur=ch[cur][0]; splay(cur); return cur; } void del(int k){ rk(k); if(cnt[rt]>1){ cnt[rt]--; maintain(rt); return; } if(!ch[rt][0]&&!ch[rt][1]){ clear(rt); rt=0; return; } if(!ch[rt][0]){ int cur=rt; rt=ch[rt][1]; fa[rt]=0; clear(cur); return; } if(!ch[rt][1]){ int cur=rt; rt=ch[rt][0]; fa[rt]=0; clear(cur); return; } int cur=rt; int x=pre(); fa[ch[cur][1]]=x; ch[x][1]=ch[cur][1]; clear(cur); maintain(rt); } }tree; int main(){ int a,b,c,d; cin>>a>>b>>c>>d; tree.ins(a); tree.ins(b); tree.ins(c); tree.ins(d); cout<<tree.kth(1); return 0; }
信息
- ID
- 705
- 时间
- 1000ms
- 内存
- 16MiB
- 难度
- 6
- 标签
- 递交数
- 17
- 已通过
- 11
- 上传者