Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 721 Solved: 272
罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人,每个人都是一个独立的团。最近举行了一次平面几何测试,每个人都得到了一个分数。 皇帝很喜欢平面几何,他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令: 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人,那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了,这条命令就忽略。 皇帝希望他每发布一条kill命令,下面的将军就把被杀的人的分数报上来。(如果这条命令被忽略,那么就报0分)
第一行一个整数n(1<=n<=1000000)。n表示士兵数,m表示总命令数。 第二行n个整数,其中第i个数表示编号为i的士兵的分数。(分数都是[0..10000]之间的整数) 第三行一个整数m(1<=m<=100000) 第3+i行描述第i条命令。命令为如下两种形式: 1. M i j 2. K i
如果命令是Kill,对应的请输出被杀人的分数。(如果这个人不存在,就输出0)
5 100 90 66 99 10 7 M 1 5 K 1 K 1 M 2 3 M 3 4 K 5 K 4
10 100 0 66
题解:呵呵呵呵呵呵呵呵呵和~~~~这不是左偏树模板题么。。
直接建立一棵左偏树乱搞搞即可。。。(不过我还是头一次写需要维护父亲节点的左偏树,看样子还有点麻烦,不过也还好,就是多几条语句)
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.