A5917. 「联合省选 2020 A | B」冰火战士
编程题
NOI/NOI+/CTSC
知识点
题目描述
一场比赛即将开始。
每位战士有两个属性：温度和能量，有两派战士：冰系战士的技能会对周围造成降温冰冻伤害，因而要求场地温度不低于他的自身温度才能参赛；火系战士的技能会对周围造成升温灼烧伤害，因而要求场地温度不高于他的自身温度才能参赛。
当场地温度确定时，双方能够参赛的战士分别排成一队。冰系战士按自身温度从低到高排序，火系战士按自身温度从高到低排序，温度相同时能量大的战士排在前面。首先，双方的第一位战士之间展开战斗，两位战士消耗相同的能量，能量少的战士将耗尽能量退出比赛，而能量有剩余的战士将继续和对方的下一位战士战斗（能量都耗尽则双方下一位战士之间展开战斗）。如此循环，直至某方战士队列为空，比赛结束。
你需要寻找最佳场地温度：使冰火双方消耗总能量最高的温度的最高值。
现在，比赛还处于报名阶段，目前还没有任何战士报名，接下来你将不断地收到报名信息和撤回信息。其中，报名信息包含报名战士的派系和两个属性，撤回信息包含要撤回的报名信息的序号。每当报名情况发生变化（即收到一条信息）时，你需要立即报出当前局面下的最佳场地温度，以及该场地温度下双方消耗的总能量之和是多少。若当前局面下无论何种温度都无法开展比赛（某一方没有战士能参赛），则只要输出
每位战士有两个属性：温度和能量，有两派战士：冰系战士的技能会对周围造成降温冰冻伤害，因而要求场地温度不低于他的自身温度才能参赛；火系战士的技能会对周围造成升温灼烧伤害，因而要求场地温度不高于他的自身温度才能参赛。
当场地温度确定时，双方能够参赛的战士分别排成一队。冰系战士按自身温度从低到高排序，火系战士按自身温度从高到低排序，温度相同时能量大的战士排在前面。首先，双方的第一位战士之间展开战斗，两位战士消耗相同的能量，能量少的战士将耗尽能量退出比赛，而能量有剩余的战士将继续和对方的下一位战士战斗（能量都耗尽则双方下一位战士之间展开战斗）。如此循环，直至某方战士队列为空，比赛结束。
你需要寻找最佳场地温度：使冰火双方消耗总能量最高的温度的最高值。
现在，比赛还处于报名阶段，目前还没有任何战士报名，接下来你将不断地收到报名信息和撤回信息。其中，报名信息包含报名战士的派系和两个属性，撤回信息包含要撤回的报名信息的序号。每当报名情况发生变化（即收到一条信息）时，你需要立即报出当前局面下的最佳场地温度，以及该场地温度下双方消耗的总能量之和是多少。若当前局面下无论何种温度都无法开展比赛（某一方没有战士能参赛），则只要输出
Peace。输入格式
第一行一个数 $Q$，表示信息的数量。
接下来 $Q$ 行，每行为 $1\ t\ x\ y$（$t \in \{0, 1\}$， $x$ 和 $y$ 都是正整数）或 $2\ k$（$k$ 是正整数）：
$1\ t\ x\ y$ 表示一条报名信息，$t = 0$ 时报名战士是冰系，$t = 1$ 时报名战士时火系，$x$ 表示战士的自身温度，$y$ 表示战士的能量。
$2\ k$ 表示一条撤回信息，撤回的是第 $k$ 条信息。被撤回的信息一定是报名信息，已被撤回的信息不会再次被撤回。
接下来 $Q$ 行，每行为 $1\ t\ x\ y$（$t \in \{0, 1\}$， $x$ 和 $y$ 都是正整数）或 $2\ k$（$k$ 是正整数）：
$1\ t\ x\ y$ 表示一条报名信息，$t = 0$ 时报名战士是冰系，$t = 1$ 时报名战士时火系，$x$ 表示战士的自身温度，$y$ 表示战士的能量。
$2\ k$ 表示一条撤回信息，撤回的是第 $k$ 条信息。被撤回的信息一定是报名信息，已被撤回的信息不会再次被撤回。
输出格式
共 $Q$ 行，每行有两个用空格隔开的正整数，分别表示当前局面下的最佳温度和该温度下冰火双方消耗的总能量之和。
输入输出样例
输入 #1
8 1 1 103 150 1 0 100 100 1 1 102 150 1 0 103 300 2 1 1 1 101 100 1 1 104 350 1 0 100 400
输出 #1
Peace 103 200 103 200 103 300 102 200 102 200 104 700 102 1000
说明/提示
$10\%$ 的数据：$Q\le 100, x\le 10^3$。
另有 $20\%$ 的数据：$Q \le 10^4, x\le 5000$，不存在撤回信息，且输入的 $x$ 按顺序不降。
$60\%$ 的数据（包含上述 $20\%$，下同）：$Q\le 2\times 10^5, x\le 2\times 10^5$。
$90\%$ 的数据：$Q\le 2\times 10^6, x\le 2\times 10^6$。
$100\%$ 的数据：$Q\le 2\times 10^6, x\le 2\times 10^9$，所有 $y$ 之和不超过 $2\times 10^9$，保证不存在 $t,x,y$ 完全相同的两个战士。
另有 $20\%$ 的数据：$Q \le 10^4, x\le 5000$，不存在撤回信息，且输入的 $x$ 按顺序不降。
$60\%$ 的数据（包含上述 $20\%$，下同）：$Q\le 2\times 10^5, x\le 2\times 10^5$。
$90\%$ 的数据：$Q\le 2\times 10^6, x\le 2\times 10^6$。
$100\%$ 的数据：$Q\le 2\times 10^6, x\le 2\times 10^9$，所有 $y$ 之和不超过 $2\times 10^9$，保证不存在 $t,x,y$ 完全相同的两个战士。