1455: 罗马游戏

 1 /**************************************************************
 2     Problem: 1455
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:4028 ms
 7     Memory:35384 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n:longint;
12    a,lef,rig,fix,fat,mak:array[0..1500000] of longint;
13    ch:char;
14 function min(x,y:longint):longint;
15          begin
16               if x<y then min:=x else min:=y;
17          end;
18 function max(x,y:longint):longint;
19          begin
20               if x>y then max:=x else max:=y;
21          end;
22 procedure swap(var x,y:longint);
23           var z:longint;
24           begin
25                z:=x;x:=y;y:=z;
26           end;
27 procedure merge(var x,y:longint);
28           begin
29                if x=0 then
30                   begin
31                        fat[y]:=fat[x];fat[x]:=0;
32                        swap(x,y);
33                   end;
34                if y=0 then exit;
35                if a[y]<a[x] then
36                   begin
37                        fat[y]:=fat[x];fat[x]:=0;
38                        swap(x,y);
39                   end;
40                merge(rig[x],y);
41                fat[rig[x]]:=x;
42                fix[x]:=min(fix[lef[x]],fix[rig[x]])+1;
43                if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);
44           end;
45 function getfat(x:longint):longint;
46          begin
47               while fat[x]<>0 do x:=fat[x];
48               exit(x);
49          end;
50 begin
51      readln(n);
52      fillchar(lef,sizeof(lef),0);
53      fillchar(rig,sizeof(rig),0);
54      fillchar(fix,sizeof(fix),0);
55      fillchar(fat,sizeof(fat),0);
56      fillchar(mak,sizeof(mak),0);
57      for i:=1 to n do read(a[i]);
58      readln;
59      readln(m);
60      for i:=1 to m do
61          begin
62               read(ch);
63               case upcase(ch) of
64                    ‘M‘:begin
65                             readln(j,k);
66                             if (mak[j]=1) or (mak[k]=1) then continue;
67                             j:=getfat(j);k:=getfat(k);
68                             if j=k then continue;
69                             merge(j,k);
70                    end;
71                    ‘K‘:begin
72                             readln(j);
73                             if mak[j]=1 then
74                                begin
75                                     writeln(0);
76                                     continue;
77                                end;
78                             j:=getfat(j);
79                             mak[j]:=1;
80                             writeln(a[j]);
81                             merge(lef[j],rig[j]);
82                             j:=lef[j];
83                             fat[j]:=0;
84                    end;
85               end;
86          end;
87      readln;
88 end.