3417. [统一省选 2020]冰火战士

【题目描述】

  一场比赛即将开始。

  每位战士有两个属性：温度和能量，有两派战士：冰系战士的技能会对周围造成降温冰冻伤害，因而要求场地温度不低于他的自身温度才能参赛；火系战士的技能会对周围造成升温灼烧伤害，因而要求场地温度不高于他的自身温度才能参赛。

  当场地温度确定时，双方能够参赛的战士分别排成一队。冰系战士按自身温度从低到高排序，火系战士按自身温度从高到低排序，温度相同时能量大的战士排在前面。首先，双方的第一位战士之间展开战斗，两位战士消耗相同的能量，能量少的战士将耗尽能量退出比赛，而能量有剩余的战士将继续和对方的下一位战士战斗（能量都耗尽则双方下一位战士之间展开战斗）。如此循环，直至某方战士队列为空，比赛结束。

  你需要寻找最佳场地温度：使冰火双方消耗总能量最高的温度的最高值。

  现在，比赛还处于报名阶段，目前还没有任何战士报名，接下来你将不断地收到报名信息和撤回信息。其中，报名信息包含报名战士的派系和两个属性，撤回信息包含要撤回的报名信息的序号。每当报名情况发生变化（即收到一条信息）时，你需要立即报出当前局面下的最佳场地温度，以及该场地温度下双方消耗的总能量之和是多少。若当前局面下无论何种温度都无法开展比赛（某一方没有战士能参赛），则只要输出 Peace。

【输入格式】

第一行一个数 Q，表示信息的数量。

接下来 Q 行，每行为 1 t x y（t ∈ {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 200

102 200

102 200

104 700

102 1000

【样例1解释】

为说明方便，约定：若第 k 条信息是报名信息，则该条报名信息对应战士 k。样例中含有战士 1、2、3、4、6、7、8，由于第 5 条是撤回信息，所以没有战士 5。

下面逐个解释每个输出：

1. 只有火系战士：战士 1，无法比赛，输出 Peace。

2. 温度为 100 ∼ 103 都能消耗最多的能量 200：战士 1 对阵战士 2 消耗能量 200，最佳温度为 103。

3. 温度为 100 ∼ 103 都能消耗最多的能量 200：战士 1 对阵战士 2 消耗能量 200，最佳温度为 103。

4. 温度 103 能消耗最多的能量 300：首先，战士 1 对阵战士 2 消耗能量 200；然后，战士 1 对阵战士 4 消耗能量 100，最佳温度为103。

5. 从现在起战士 1 不再存在。温度 100 ∼ 102 能消耗最多的能量 200：战士 2 对阵战士 3 消耗能量 200，最佳温度为 102。

6. 温度 100 ∼ 102 能消耗最多的能量 200：战士 2 对阵战士 3 消耗能量 200，最佳温度为 102。

7. 温度 100 ∼ 104 能消耗最多的能量 700：首先，战士 2 对阵战士 7 消耗能量 200；然后，战士 4 对阵战士 7 消耗能量 500，最佳温度为 104。

8. 温度 100 ∼ 102 能消耗最多的能量 1000：首先，战士 7 对阵战士 8 消耗能量 700；然后，战士 1 对阵战士 8 消耗能量 100；接着，战士 1 对阵战士 2 消耗能量 200，最佳温度为 102。

【样例2输入输出】

见选手目录下的 icefire/icefire2.in 与 icefire/icefire2.ans。

【提示】

10% 的数据：Q ≤ 100，x ≤ $10^3$ 。

另有 20% 的数据：Q ≤ $10^4$ ，x ≤ 5000，不存在撤回信息，且输入的 x 按顺序不降。

60% 的数据（包含上述 20%，下同）：Q ≤ 2 × $10^5$ ，x ≤ 2 × $10^5$ 。

90% 的数据：Q ≤ 2 × $10^6$ ，x ≤ 2 × $10^6$ 。

100% 的数据：1 ≤ Q ≤ 2 × $10^6$ ，1 ≤ x ≤ 2 × $10^9$ ，所有 y 之和不超过 2 × $10^9$ ，保证不存在 t,x,y 完全相同的两个战士。

【来源】

HAOI 2020 Day1 Task1