首页 > 代码库 > HDU 4006 求第k大数 treap
HDU 4006 求第k大数 treap
裸题,瞬秒。。
#include <stdio.h> #include <iostream> #include <algorithm> #include <math.h> #include <vector> #include <set> #include <map> #include <queue> using namespace std; #define L(id) tree[id].ch[0] #define R(id) tree[id].ch[1] #define Size(id) tree[id].size #define Father(id) tree[id].fa #define Val(id) tree[id].val #define ll int ll Mid(ll x,ll y){return (x+y)>>1;} #define N 30100 ll a[N], n; int ch[N][2],val[N],counts[N],r[N],size[N],tot,root; int Newnode(int &rt,int v) { rt=++tot; val[rt]=v; ch[rt][0]=ch[rt][1]=0; counts[rt]=size[rt]=1; r[rt]=rand(); return rt; } inline void PushUp(int rt) { size[rt]=size[ch[rt][0]]+size[ch[rt][1]]+counts[rt]; } void Rotate(int &x,int kind) { int y=ch[x][kind^1]; ch[x][kind^1]=ch[y][kind]; ch[y][kind]=x; PushUp(x);PushUp(y); x=y; } int Insert(int &rt,int v) { if(rt==0) return Newnode(rt,v); int ans; if(v==val[rt]) counts[rt]++, ans = rt; else { int kind=(v>val[rt]); ans = Insert(ch[rt][kind],v); if(r[ch[rt][kind]]<r[rt]) Rotate(rt,kind^1); } PushUp(rt); return ans; } int select(int rt,int k) { if(size[ch[rt][0]]>=k) return select(ch[rt][0],k); if(size[ch[rt][0]]+counts[rt]>=k) return val[rt]; return select(ch[rt][1],k-size[ch[rt][0]]-counts[rt]); } void remove(int &rt,int v) { if(val[rt]==v) { if(counts[rt]>1) counts[rt]--; else if(!ch[rt][0]&&!ch[rt][1]) {rt=0;return ;} else { int kind=r[ch[rt][0]]<r[ch[rt][1]]; Rotate(rt,kind); remove(rt,v); } } else remove(ch[rt][v>val[rt]],v); PushUp(rt); } void Init() { ch[0][0]=ch[0][1]=0; size[0]=counts[0]=val[0]=0; tot=root=0; r[0]=(1LL<<31)-1; Newnode(root,2000000001); } int q[N]; char s[2]; int main(){ int que, i, j, k, l, r; while(~scanf("%d %d",&n,&que)){ Init(); while(n--){ scanf("%s",s); if(s[0]=='I')scanf("%d",&l),Insert(root,-l); else printf("%d\n",-select(root,que)); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。