{"problem":{"name":"[北大集训 2021] 魔塔 OL","description":{"content":"比特游戏公司最近发布了一款新游戏《魔塔 Online》，玩家可以操控勇士在游戏世界中与怪物进行搏斗。在游戏发布之初，魔塔里没有任何怪物，接下来将依次发生 $q$ 个事件，每个事件是以下三种之一： * `+ x y z a b`：表示游戏发布了新版本，在游戏中新增了一只怪物。如果这是第一只新增的怪物，那么它的编号为 $1$；否则它的编号为最后一只新增的怪物的编号 $+1$。这只怪物位于魔塔的第 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8985"},"statements":[{"statement_type":"Markdown","content":"比特游戏公司最近发布了一款新游戏《魔塔 Online》，玩家可以操控勇士在游戏世界中与怪物进行搏斗。在游戏发布之初，魔塔里没有任何怪物，接下来将依次发生 $q$ 个事件，每个事件是以下三种之一：\n\n* `+ x y z a b`：表示游戏发布了新版本，在游戏中新增了一只怪物。如果这是第一只新增的怪物，那么它的编号为 $1$；否则它的编号为最后一只新增的怪物的编号 $+1$。这只怪物位于魔塔的第 $x$ 层，它的等级为 $y$ 级，它的难度为 $z$。如果玩家选择击杀这只怪物，那么需要消耗 $a$ 点血量，在击杀成功后，玩家将得到一支可以恢复 $b$ 点血量的药剂并立即使用。\n* `- k`：表示游戏发布了新版本，编号为 $k$ 的怪物由于平衡性问题下架，它将不会出现在魔塔中。请注意：下架的怪物**仍然保留它们的编号**，未来新增的怪物**不会复用**被下架怪物的编号。\n* `? g l d`：表示一个询问。某玩家希望击杀魔塔前 $g$ 层中**所有**等级**不超过** $l$ 且难度**不超过** $d$ 的怪物。玩家可以按照**任意顺序**去击杀这些怪物，登上新的一层**不需要杀光**当前层的所有怪物，且作战过程中不会受到别的怪物的干扰。你的任务是帮助该玩家计算出征前勇士的血量**最少**是多少。如果某个时刻勇士的血量是**负数**，那么游戏结束，你一定要防止这种情况的发生。\n\n请写一个程序，依次回答每个询问。注意：每个询问只是玩家的一个思考，**不会真正击杀**任何一只怪物。\n\n## Input\n\n输入的第一行包含一个整数 $q$，表示事件数。\n\n接下来 $q$ 行，每行开头一个字符，随后是几个整数，依次描述每个事件。\n\n输入数据保证 $1\\leq q\\leq 150\\,000$，怪物总数不超过 $50\\,000$，询问数量不超过 $50\\,000$。\n\n对于新增怪物操作，保证 $1\\leq x,y,z\\leq 10\\,000$，且 $0\\leq a,b\\leq 10^9$。\n\n对于下架怪物操作，保证操作合法，且每只怪物不会被重复下架。\n\n对于询问，保证 $1\\leq g,l,d\\leq 10\\,000$。\n\n## Output\n\n对于每个询问，输出一行一个整数，即出征前勇士的血量的最小值。\n\n[samples]\n\n## Background\n\nCTT2021 D1T2\n\n## Note\n\n1. （3 分）怪物总数不超过 $8$，询问数量不超过 $8$。\n2. （7 分）怪物总数不超过 $5\\,000$，询问数量不超过 $5\\,000$。\n3. （10 分）药剂不会回血，且所有怪物的难度都是 $1$。即 $b=0$，且 $z=d=1$。\n4. （17 分）$1\\leq x,y,z,g,l,d\\leq 5$。\n5. （30 分）所有怪物的等级和难度都是 $1$。即 $y=z=l=d=1$。\n6. （33 分）无其他限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8985","tags":["2021","O2优化","CTT（清华集训/北大集训）"],"sample_group":[["10\n+ 2 1 1 3 4\n+ 1 2 2 2 5\n? 2 2 2\n+ 1 1 1 8 2\n? 2 2 1\n? 1 2 2\n- 1\n? 2 2 2\n- 3\n? 1 2 2\n","2\n7\n5\n5\n2\n"]],"created_at":"2026-03-03 11:09:25"}}