P8985 [北大集训 2021] 魔塔 OL
题目背景
CTT2021 D1T2
题目描述
比特游戏公司最近发布了一款新游戏《魔塔 Online》,玩家可以操控勇士在游戏世界中与怪物进行搏斗。在游戏发布之初,魔塔里没有任何怪物,接下来将依次发生 $q$ 个事件,每个事件是以下三种之一:
* `+ x y z a b`:表示游戏发布了新版本,在游戏中新增了一只怪物。如果这是第一只新增的怪物,那么它的编号为 $1$;否则它的编号为最后一只新增的怪物的编号 $+1$。这只怪物位于魔塔的第 $x$ 层,它的等级为 $y$ 级,它的难度为 $z$。如果玩家选择击杀这只怪物,那么需要消耗 $a$ 点血量,在击杀成功后,玩家将得到一支可以恢复 $b$ 点血量的药剂并立即使用。
* `- k`:表示游戏发布了新版本,编号为 $k$ 的怪物由于平衡性问题下架,它将不会出现在魔塔中。请注意:下架的怪物**仍然保留它们的编号**,未来新增的怪物**不会复用**被下架怪物的编号。
* `? g l d`:表示一个询问。某玩家希望击杀魔塔前 $g$ 层中**所有**等级**不超过** $l$ 且难度**不超过** $d$ 的怪物。玩家可以按照**任意顺序**去击杀这些怪物,登上新的一层**不需要杀光**当前层的所有怪物,且作战过程中不会受到别的怪物的干扰。你的任务是帮助该玩家计算出征前勇士的血量**最少**是多少。如果某个时刻勇士的血量是**负数**,那么游戏结束,你一定要防止这种情况的发生。
请写一个程序,依次回答每个询问。注意:每个询问只是玩家的一个思考,**不会真正击杀**任何一只怪物。
输入格式
无
输出格式
无
说明/提示
1. (3 分)怪物总数不超过 $8$,询问数量不超过 $8$。
2. (7 分)怪物总数不超过 $5\,000$,询问数量不超过 $5\,000$。
3. (10 分)药剂不会回血,且所有怪物的难度都是 $1$。即 $b=0$,且 $z=d=1$。
4. (17 分)$1\leq x,y,z,g,l,d\leq 5$。
5. (30 分)所有怪物的等级和难度都是 $1$。即 $y=z=l=d=1$。
6. (33 分)无其他限制。