POJ 1442 Black Box treap裸题 动态求整个序列的前k大数
发布时间:2020-12-14 03:37:07 所属栏目:大数据 来源:网络整理
导读:#include stdio.h#include iostream#include algorithm#include math.h#include vector#include set#include map#include queueusing namespace std;#define L(id) tree[id].ch[0]#define R(id) tree[id].ch[1]#define Size(id) tree[id].size#define Father
#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]; int main(){ int que,i,j,k,l,r; while(~scanf("%d %d",&n,&que)){ Init(); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=que;i++)scanf("%d",&q[i]); int s = 1,cnt = 0; for(i=1;i<=n;i++) { Insert(root,a[i]); if(s>n)break; while(size[root]-1 == q[s]) { printf("%dn",select(root,++cnt)); s++; } } } return 0; } /* 7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3 */ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |