몽키 킹 왼쪽 편나무

제목 링크:HDU - 1512
Once in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can't avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.
Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2).
And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.
Input
There are several test cases, and each case consists of two parts.
First part: The first line contains an integer N(N<=100,000), which indicates the number of monkeys. And then N lines follows. There is one number on each line, indicating the strongness value of ith monkey(<=32768).
Second part: The first line contains an integer M(M<=100,000), which indicates there are M conflicts happened. And then M lines follows, each line of which contains two integers x and y, indicating that there is a conflict between the Xth monkey and Yth.
Output
For each of the conflict, output -1 if the two monkeys know each other, otherwise output the strongness value of the strongest monkey in all friends of them after the duel.
 
제목 묘사: n마리의 원숭이가 있는데, 원숭이 한 마리당 가치가 있고, 두 마리의 원숭이가 싸우면 그들의 가치가 각각 반으로 떨어진다.m개의 사건을 제시하고 각 사건마다 두 마리의 원숭이를 제시한다. 만약에 두 마리의 원숭이가 모르면 싸움이 끝나면 친구가 된다(두 마리의 원숭이의 각자 친구도 서로 친구가 된다). 싸움이 끝난 후 두 마리의 원숭이의 모든 친구 중 가장 큰 값을 구한다.
알고리즘 분석: 이 문제를 제가 처음 시작했을 때 생각하고 수집을 했는데 이 정도면 충분할 줄 알았어요. (사실 시간 복잡도는 저도 직시할 수 없어요.) 과감한 TLE를 제출했어요. 나중에 토론을 봤는데 니마, 이게 바로 전설의 왼쪽 나무의 제목이에요. 과감하게 공부를 해서 자신의 데이터 구조에 대한 지식을 보완해야 해요.
설명: 처음으로 왼쪽 편나무를 만들었는데 코드는 다른 사람을 참고한 것이지만 진심으로 쓴 것이 비교적 좋아서 가져왔다.그리고 훈련팀의 논문을 추천해 주세요. 기본적으로 논문을 보고 왼쪽 편나무에 대해 어느 정도 알게 됐어요.
왼쪽 편향 나무의 특징과 응용
 

 1 /* */

 2 #include<iostream>

 3 #include<cstdio>

 4 #include<cstdlib>

 5 #include<cstring>

 6 #include<cmath>

 7 #include<algorithm>

 8 #define inf 0x7fffffff

 9 using namespace std;

10 const int maxn = 100000+10;

11 

12 int father[maxn];

13 struct node

14 {

15     int l,r;

16     int dis;

17     int strong;

18 }LTree[maxn];

19 int Find(int x)

20 {

21     if (father[x]==x) return x;

22     return father[x]=Find(father[x]);

23 }

24 int Merge(int x,int y)

25 {   // 

26     if (x==0) return y;

27     if (y==0) return x;

28     if (LTree[x].strong < LTree[y].strong)            // 

29         swap(x,y);

30     LTree[x].r = Merge(LTree[x].r,y);            // Y

31     int l = LTree[x].l , r = LTree[x].r;

32     father[r] = x;                        // T 

33     if (LTree[l].dis < LTree[r].dis)                // 

34         swap(LTree[x].l,LTree[x].r);

35     if (LTree[x].r == 0)                    //   0

36         LTree[x].dis = 0;

37     else

38         LTree[x].dis = LTree[LTree[x].r].dis + 1;

39     return x;

40 }

41 int del(int x)

42 {   // 

43     int l,r;

44     l=LTree[x].l;

45     r=LTree[x].r;

46     father[l]=l;

47     father[r]=r;

48     LTree[x].l=LTree[x].r=LTree[x].dis=0;

49     return Merge(l,r);

50 }

51 void solve(int x,int y)

52 {

53     LTree[x].strong /= 2;

54     LTree[y].strong /= 2;

55     // PK ， 。

56     int left,right;

57     left = del(x);

58     right = del(y);

59     left = Merge(left,x);

60     right = Merge(right,y);

61     left = Merge(left,right);

62     printf("%d
",LTree[left].strong);

63 }

64 int main()

65 {

66     int n,m,x,y;

67     while (scanf("%d",&n)!=EOF)

68     {

69         for (int i=1 ;i<=n ;i++)

70         {

71             scanf("%d",&LTree[i].strong);

72             LTree[i].l=0;

73             LTree[i].r=0;

74             LTree[i].dis=0;

75             father[i]=i;            // 

76         }

77         scanf("%d",&m);

78         for (int i=1 ;i<=m ;i++)

79         {

80             scanf("%d%d",&x,&y);

81             int fx=Find(x),fy=Find(y);

82             if (fx == fy) printf("-1
");

83             else solve(fx,fy);

84         }

85     }

86     return 0;

87 }