1455: 罗马游戏

1455: 罗马游戏

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 721  Solved: 272

[Submit][Status][Discuss]

Description

罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人,每个人都是一个独立的团。最近举行了一次平面几何测试,每个人都得到了一个分数。 皇帝很喜欢平面几何,他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令: 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人,那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了,这条命令就忽略。 皇帝希望他每发布一条kill命令,下面的将军就把被杀的人的分数报上来。(如果这条命令被忽略,那么就报0分)

Input

第一行一个整数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

Output

如果命令是Kill,对应的请输出被杀人的分数。(如果这个人不存在,就输出0)

Sample Input

5 100 90 66 99 10 7 M 1 5 K 1 K 1 M 2 3 M 3 4 K 5 K 4

Sample Output

10 100 0 66

HINT

Source

题解:呵呵呵呵呵呵呵呵呵和~~~~这不是左偏树模板题么。。

直接建立一棵左偏树乱搞搞即可。。。(不过我还是头一次写需要维护父亲节点的左偏树,看样子还有点麻烦,不过也还好,就是多几条语句)

 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.    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

ExtJs学习笔记(3)_GridPanel[XML做数据源]

这一节,将学习到除了用JSON做GridPanel的数据源外,还可以使用XML 一。静态示例 1.xml文件内容: <?xml version="1.0...

2248
来自专栏Y大宽

RNA-seq数据分析工具详细介绍(从质量控制到可视化)

2573
来自专栏WindCoder

Best Programming Editors? A Never Ending Battle With No Clear Winner

原文:Best Programming Editors? A Never Ending Battle With No Clear Winner

701
来自专栏用户2442861的专栏

Android游戏开发十日通(6)- 太空大战

http://blog.csdn.net/silangquan/article/details/16921035

1212
来自专栏10km的专栏

Ubuntu16:cmake生成Makefile编译caffe过程(OpenBLAS/CPU+GPU)塈解决nvcc warning:The 'compute_20', 'sm_20'

之前在ubuntu14下实现了Caffe编译(参见去年写的博客 《 Ubuntu14:cmake生成Makefile编译caffe过程(OpenBLAS/CPU...

4768
来自专栏码匠的流水账

聊聊lettuce的指标监控

lettuce-core-5.0.4.RELEASE-sources.jar!/io/lettuce/core/event/metrics/DefaultCom...

2592
来自专栏智能计算时代

Microservices Ecosystem Transit Map

…we assembled a map of the ecosystem to help guide practitioners, vendors, inves...

3794
来自专栏GIS讲堂

Arcgis for JS实现台风运动路径与影像范围的显示

3332
来自专栏GIS讲堂

Openlayers2中统计图的实现

在前文中,介绍了Arcgis for js和Openlayers3中统计图的实现,在本文,书接上文,介绍在Openlayers2中,统计图的实现。

1353
来自专栏菩提树下的杨过

Silverlight Telerik控件学习:GridView双向绑定

做过WinForm数据库开发的人,一定有类似经历:DataGrid绑定后,如果允许行编辑,数据一顿修改后,想批量保存修改后的结果,通常是将DataGrid的所有...

2255

扫码关注云+社区

领取腾讯云代金券