首页 > 代码库 > 【裸裸的左偏树】BZOJ1455-罗马游戏
【裸裸的左偏树】BZOJ1455-罗马游戏
【题目大意】
给出一些数和一些操作。M：合并两个数所在的集合，如果有任意一个数被删除则忽略操作；K：删除某个数所在集合中最小的数。
【思路】
裸裸的，复习^ ^
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=1000000+500; 7 struct node 8 { 9 int key,dis,del; 10 int lson,rson,father; 11 }ltree[MAXN]; 12 int n,m; 13 14 int find(int a) 15 { 16 while (ltree[a].father!=a) a=ltree[a].father; 17 return a; 18 } 19 20 void build(int rt,int val) 21 { 22 ltree[rt].key=val; 23 ltree[rt].dis=(rt==0)?-1:0; 24 ltree[rt].del=0; 25 ltree[rt].lson=ltree[rt].rson=0; 26 ltree[rt].father=rt; 27 } 28 29 int merge(int x,int y) 30 { 31 if (x==0||y==0) return (x|y); 32 if (ltree[x].key>ltree[y].key) swap(x,y); 33 ltree[x].rson=merge(ltree[x].rson,y); 34 int &l=ltree[x].lson,&r=ltree[x].rson; 35 ltree[l].father=ltree[r].father=x; 36 if (ltree[l].dis<ltree[r].dis) swap(l,r); 37 if (r==0) ltree[x].dis=0; 38 else ltree[x].dis=ltree[r].dis+1; 39 return x; 40 } 41 42 void Del(int rt) 43 { 44 int l=ltree[rt].lson,r=ltree[rt].rson; 45 ltree[l].father=l; 46 ltree[r].father=r; 47 ltree[rt].dis=ltree[rt].lson=ltree[rt].rson=0; 48 ltree[rt].del=1; 49 merge(l,r); 50 } 51 52 void init() 53 { 54 scanf("%d",&n); 55 for (int i=1;i<=n;i++) 56 { 57 int score; 58 scanf("%d",&score); 59 build(i,score); 60 } 61 build(0,0); 62 } 63 64 void solve() 65 { 66 scanf("%d",&m); 67 for (int i=0;i<m;i++) 68 { 69 char op[1]; 70 scanf("%s",op); 71 if (op[0]==‘M‘) 72 { 73 int a,b; 74 scanf("%d%d",&a,&b); 75 if (!ltree[a].del&&!ltree[b].del) 76 { 77 int fa=find(a),fb=find(b); 78 if (fa!=fb) merge(fa,fb);//不要忘记要判断两者不在同一个集合中 79 } 80 } 81 if (op[0]==‘K‘) 82 { 83 int a; 84 scanf("%d",&a); 85 if (ltree[a].del) puts("0"); 86 else 87 { 88 int fa=find(a); 89 printf("%d\n",ltree[fa].key); 90 Del(fa); 91 } 92 } 93 } 94 } 95 96 int main() 97 { 98 init(); 99 solve();100 return 0;101 }
【裸裸的左偏树】BZOJ1455-罗马游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。