【NOIP模拟赛】魔兽争霸

2014年10月6日1,8581

小x正在销魂地玩魔兽

他正控制着死亡骑士和n个食尸鬼(编号1~n)去打猎

 

死亡骑士有个魔法,叫做“死亡缠绕”,可以给食尸鬼补充HP

战斗过程中敌人会对食尸鬼实施攻击,食尸鬼的HP会减少

 

小x希望随时知道自己部队的情况,即HP值第k多的食尸鬼有多少HP,以便决定如何施放魔法

请同学们帮助他:)

 

小x向你发出3种信号:(下划线在输入数据中表现为空格)

A_i_a表示敌军向第i个食尸鬼发出了攻击,并使第i个食尸鬼损失了a点HP,如果它的HP<=0,那么这个食尸鬼就死了(Undead也是要死的……)。

敌军不会攻击一个已死的食尸鬼。

C_i_a 表示死亡骑士向第i个食尸鬼放出了死亡缠绕,并使其增加了a点HP。

HP值没有上限。

死亡骑士不会向一个已死的食尸鬼发出死亡缠绕

Q_k  表示小x向你发出询问

 

输入(war.in)

第一行,一个正整数 n

以后n个整数 表示n个食尸鬼的初始HP值

接着一个正整数m

以下m行 每行一个小x发出的信号

 

输出(war.out)

对于小x的每个询问,输出HP第k多的食尸鬼有多少HP,如果食尸鬼总数不足k个,输出-1。每个一行数。

最后一行输出一个数:战斗结束后剩余的食尸鬼数

 

样例

Input Output
51 2 3

4 5

10

Q 2

A 4 6

C 1 4

Q 2

A 2 1

A 3 3

A 1 3

Q 4

C 2 10

Q 1

45

-1

11

3

 

 

约定

40%的数据  n<=3000  m<=5000

70%的数据  n<=8000  m<=10000

100%的数据  n<=30000  m<=50000

90%的数据随机生成

食尸鬼HP没有上限

数据保证任意时刻食尸鬼的HP值在longint范围内

数据保证A和C命令中的食尸鬼是活着的

输入数据中没有多余空格、换行

题解

部分分快排。。

正解平衡树

 

  • cyy2015年7月13日 下午1:19 回复

    突然想吐槽C党的标准库,P党泪奔呀=_=….

    #1