题意：
每次添加一个数在集合中，并寻找这个数在集合排序后的前驱和后继
treap模版水题
//treap //插入、删除、查询数排名、查询第k小、查询前驱与后继、查询树大小 #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <queue> #include <map> #include <set> #include <vector> using namespace std; #include <iostream> using namespace std; #define MAXN 200010 struct node { int id,val; node() {} node(int a,int b) { id=a,val=b; }; bool operator>(const node &b) const { return val>b.val; } }; struct data { int l,r,size,rnd,w; node v; }; class tp { public: int n,size,root; node ans; tp() { n=root=0; size=0; } data tr[MAXN]; void update(int k)//更新结点信息 { tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w; } void init() { n=root=0; size=0; memset(tr,0,sizeof tr); } void rturn(int &k) { int t=tr[k].l; tr[k].l=tr[t].r; tr[t].r=k; tr[t].size=tr[k].size; update(k); k=t; } void lturn(int &k) { int t=tr[k].r; tr[k].r=tr[t].l; tr[t].l=k; tr[t].size=tr[k].size; update(k); k=t; } void insert(int &k,node x) { if(k==0) { size++; k=size; tr[k].size=tr[k].w=1; tr[k].v=x; tr[k].rnd=rand(); return; } tr[k].size++; /*if(tr[k].v==x)tr[k].w++;//每个结点顺便记录下与该节点相同值的数的个数 else */if(x>tr[k].v) { insert(tr[k].r,x); if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);//维护堆性质 } else { insert(tr[k].l,x); if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k); } } void del(int &k,node& x)// 删除x数(若有多个相同的数，因只删除一个) { if(k==0)return; /* if(tr[k].v==x) { if(tr[k].w>1) { tr[k].w--; tr[k].size--; return;//若不止相同值的个数有多个，删去一个 } if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;//有一个儿子为空 else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd) rturn(k),del(k,x); else lturn(k),del(k,x); } else*/ if(x>tr[k].v) tr[k].size--,del(tr[k].r,x); else tr[k].size--,del(tr[k].l,x); } void query_pro(int k,node& x)//求x的前驱(前驱定义为小于x，且最大的数) { if(k==0)return; if(x>tr[k].v) { ans=tr[k].v; query_pro(tr[k].r,x); } else query_pro(tr[k].l,x); } void query_sub(int k,node& x)//求x的后继(后继定义为大于x，且最小的数) { if(k==0)return; if(tr[k].v>x) { ans=tr[k].v; query_sub(tr[k].l,x); } else query_sub(tr[k].r,x); } }; tp sb; int main() { int n; int a,b; while(scanf("%d", &n)!=EOF) { if (!n)break; sb.init(); sb.insert(sb.root,node(0,-1e9)); sb.insert(sb.root,node(1,1e9)); node tmp; for(int i = 1; i <= n; i++) { scanf("%d%d",&a,&b); tmp.id=a,tmp.val=b; sb.insert(sb.root,tmp); sb.query_pro(sb.root,tmp); node up=sb.ans; sb.query_sub(sb.root,tmp); node dn=sb.ans; int dif1=abs(up.val-b); int dif2=abs(dn.val-b); if (dif1<=dif2) printf("%d %d\n",a,up.id); else if (dif1>dif2) printf("%d %d\n",a,dn.id); } } return 0; }
