#P8985. [北大集训 2021] 魔塔 OL

[北大集训 2021] 魔塔 OL

题目背景

CTT2021 D1T2

题目描述

比特游戏公司最近发布了一款新游戏《魔塔 Online》,玩家可以操控勇士在游戏世界中与怪物进行搏斗。在游戏发布之初,魔塔里没有任何怪物,接下来将依次发生 qq 个事件,每个事件是以下三种之一:

  • + x y z a b:表示游戏发布了新版本,在游戏中新增了一只怪物。如果这是第一只新增的怪物,那么它的编号为 11;否则它的编号为最后一只新增的怪物的编号 +1+1。这只怪物位于魔塔的第 xx 层,它的等级为 yy 级,它的难度为 zz。如果玩家选择击杀这只怪物,那么需要消耗 aa 点血量,在击杀成功后,玩家将得到一支可以恢复 bb 点血量的药剂并立即使用。
  • - k:表示游戏发布了新版本,编号为 kk 的怪物由于平衡性问题下架,它将不会出现在魔塔中。请注意:下架的怪物仍然保留它们的编号,未来新增的怪物不会复用被下架怪物的编号。
  • ? g l d:表示一个询问。某玩家希望击杀魔塔前 gg 层中所有等级不超过 ll 且难度不超过 dd 的怪物。玩家可以按照任意顺序去击杀这些怪物,登上新的一层不需要杀光当前层的所有怪物,且作战过程中不会受到别的怪物的干扰。你的任务是帮助该玩家计算出征前勇士的血量最少是多少。如果某个时刻勇士的血量是负数,那么游戏结束,你一定要防止这种情况的发生。

请写一个程序,依次回答每个询问。注意:每个询问只是玩家的一个思考,不会真正击杀任何一只怪物。

输入格式

输入的第一行包含一个整数 qq,表示事件数。

接下来 qq 行,每行开头一个字符,随后是几个整数,依次描述每个事件。

输入数据保证 1q1500001\leq q\leq 150\,000,怪物总数不超过 5000050\,000,询问数量不超过 5000050\,000

对于新增怪物操作,保证 1x,y,z100001\leq x,y,z\leq 10\,000,且 0a,b1090\leq a,b\leq 10^9

对于下架怪物操作,保证操作合法,且每只怪物不会被重复下架。

对于询问,保证 1g,l,d100001\leq g,l,d\leq 10\,000

输出格式

对于每个询问,输出一行一个整数,即出征前勇士的血量的最小值。

10
+ 2 1 1 3 4
+ 1 2 2 2 5
? 2 2 2
+ 1 1 1 8 2
? 2 2 1
? 1 2 2
- 1
? 2 2 2
- 3
? 1 2 2

2
7
5
5
2

提示

  1. (3 分)怪物总数不超过 88,询问数量不超过 88
  2. (7 分)怪物总数不超过 50005\,000,询问数量不超过 50005\,000
  3. (10 分)药剂不会回血,且所有怪物的难度都是 11。即 b=0b=0,且 z=d=1z=d=1
  4. (17 分)1x,y,z,g,l,d51\leq x,y,z,g,l,d\leq 5
  5. (30 分)所有怪物的等级和难度都是 11。即 y=z=l=d=1y=z=l=d=1
  6. (33 分)无其他限制。