POJ 2352 Stars Treap

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

题目链接：http://poj.org/problem?id=2352

代码：

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#define sf scanf
#define pf printf
using namespace std;
const int maxn = 15000 + 50,INF = 0x7fffffff;
#define lson rt][0
#define rson rt][1
int ch[maxn][2],fix[maxn],fa[maxn],size[maxn];
int tot,root,sroot;
int key[maxn];
void Treap_Init(){tot = 1;sroot = 0;memset(ch[0] ,0,sizeof ch[0]);fa[0] = 0;fix[0] = INF;size[0] = 0;key[0] = INF;
}
int NewNode(int FA,int k){fa[tot] = FA;memset(ch[tot],0,sizeof ch[tot]);fix[tot] = rand();size[tot] = 1;key[tot] = k;return tot++;
}
void PushUp(int rt){size[rt] = 1 + size[ch[rt][1]] + size[ch[rt][0]];if(rt == sroot) size[rt] = 0;
}
void rotate(int rt,int kind){int prt = fa[rt];ch[prt][kind] = ch[rt][!kind];fa[ch[rt][!kind]] = prt;ch[fa[prt]][ ch[fa[prt]][1] == prt ] = rt;fa[rt] = fa[prt];ch[rt][!kind] = prt;fa[prt] = rt;PushUp(prt);PushUp(rt);
}
void Insert(int k){int rt = root;while( ch[rt][k >= key[rt]] ) 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]])rotate(rt,ch[fa[rt]][1] == rt);if(fa[rt] == sroot) root = rt;while(fa[rt] != sroot){PushUp(rt);rt = fa[rt];}
}
void Delete(int rt,int k){if(key[rt] == k){if(ch[rt][0] && ch[rt][1]){int nrt = ch[rt][0];if(size[nrt] < size[ch[rt][1]]) nrt = ch[rt][1];rotate(nrt,ch[rt][ ch[rt][1] == nrt ]);size[nrt]--;Delete(rt,k);}else{int nrt;if(ch[rt][0]) nrt = ch[rt][0];else nrt = ch[rt][1];fa[nrt] = fa[rt];ch[fa[rt]][ ch[fa[rt]][1] == rt ] = nrt;}}else{size[rt]--;Delete(ch[rt][k > key[rt]],k);}
}int getRank(int rt,int k){if(rt == sroot) return 0;if(k >= key[rt]) return size[ch[rt][0]] + (key[rt] <= k) + getRank(ch[rt][1],k);else return getRank(ch[rt][0],k);
}int ans[maxn];
int main(){
//    freopen("rand.txt","r",stdin);int n;while( ~sf("%d",&n) ){Treap_Init();int x,y;memset(ans , 0 ,sizeof ans);for(int i = 0;i < n;++i){sf("%d %d",&x,&y);y = getRank(root,x);ans[getRank(root,x)]++;Insert(x);}for(int i = 0;i < n;++i){pf("%d\n",ans[i]);}}
}

这篇关于POJ 2352 Stars Treap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---