首页 > 代码库 > POJ 2352 treap
POJ 2352 treap
当年经常遇到这种题，愣是没做出来，好像那时不会线段树，也不会平衡树。
凭借一身蛮力来搞，倒是和那群朋友搞得开开心心。
题意：
y从小到大，若y相同，x从小到大，这样给出一些坐标，求每个点覆盖的点个数。
题解：
每次只需计算小于等于当前x值得个数有多少即可。
可用线段树或平衡树做，现在平衡树treap也是做了一定题了，比起线段树反而写起来更溜！
爽！
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#include <ctime>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define MAXN 20005using namespace std;int cnt=1, rt=0;int n,ans[MAXN],x,y;struct Tree{ int key, pri, size, son[2]; void set(int x, int y, int z) { key=x; pri=y; size=z; son[0]=son[1]=0; }}T[MAXN];void rotate(int p, int &x){ int y=T[x].son[!p]; T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size; T[x].son[!p]=T[y].son[p]; T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size; T[y].son[p]=x; x=y;}void ins(int key, int &x){ if(x == 0) T[x = cnt++].set(key, rand(), 1); else { T[x].size++; int p=key <= T[x].key; ins(key, T[x].son[!p]); if(T[x].pri > T[T[x].son[!p]].pri) rotate(p, x); }}int find(int key, int &x){ if(x == 0) return 0; if(T[x].key <= key) return T[T[x].son[0]].size+1+find(key, T[x].son[1]); else return find(key, T[x].son[0]);}int main(){ scanf("%d", &n); for(int i=0; i<n; i++) { scanf("%d%d", &x, &y); ans[find(x, rt)]++; ins(x, rt); } for(int i=0; i<n; i++) printf("%d\n", ans[i]); return 0;}
POJ 2352 treap
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。