POJ 1442 Black Box Treap 模板题

本文主要是介绍POJ 1442 Black Box Treap 模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=1442
给两个序列A,B
求A中前B[i]个数第i小的数是几

poj不支持srand(time(NULL)) RE的可能是这个原因
代码：

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define sf scanf
#define pf printfusing namespace std;
const int maxn = 444444 + 50;/** Treap */
int ch[maxn][2],size[maxn],fa[maxn],fix[maxn],key[maxn];
int root,sroot,tot;
inline void Treap_Init(){sroot = root = 0;fa[root] = sroot;ch[root][0] = ch[root][1] = 0;size[sroot] = 0;tot = 1;
}inline void PushUp(int rt){size[rt] = 1 + size[ch[rt][0]] + size[ch[rt][1]];
}inline int NewNode(int FA,int k){fa[tot] = FA;ch[tot][0] = ch[tot][1] = sroot;size[tot] = 1;fix[tot] = rand();key[tot] = k;return tot++;
}inline void rotate(int rt,int kind){int prt = fa[rt];ch[prt][kind] = ch[rt][!kind];fa[ch[rt][!kind]] = prt;if(fa[prt]!=sroot)ch[ fa[prt] ][ ch[fa[prt]][1] == prt ] = rt;fa[rt] = fa[prt];ch[rt][!kind] = prt;fa[prt] = rt;
}inline void Insert(int k){int rt = root;while( ch[rt][ (k >= key[rt]) ] != sroot){rt = ch[rt][ (k >= key[rt]) ];}ch[rt][ k >= key[rt] ] = NewNode(rt,k);rt = ch[rt][ k >= key[rt] ];while( (fa[rt] != sroot) && (fix[rt] >= fix[fa[rt]]) ){int prt = fa[rt];rotate(rt,ch[fa[rt]][1] == rt);PushUp(prt);PushUp(rt);}if(fa[rt] == sroot) root = rt;while( fa[rt] != sroot ){rt = fa[rt];PushUp(rt);}
}inline int Search(int k){int rt = root;while( true ){if(k <= size[ch[rt][0]]) rt = ch[rt][0];else if(k > size[ch[rt][0]] + 1) {k -= size[ch[rt][0]] + 1;rt = ch[rt][1];}else return key[rt];}
}int num[maxn];
int main(){
//    freopen("in.txt","r",stdin);int n,m,cur,tmp;while( ~sf("%d%d",&n,&m) ){Treap_Init();for(int i = 1;i <= n;++i) sf("%d",&num[i]);cur = 0;for(int i = 1;i <= m;++i){sf("%d",&tmp);while(cur < tmp){Insert(num[++cur]);}pf("%d\n",Search(i));}}
}