题意分析
记 $\mathrm{ice}$ 表示冰系战士，$\mathrm{fire}$ 表示火系战士。
记 $\operatorname{ice}(t),\operatorname{fire}(t)$ 分别表示温度为 $t$ 的时候，能出战的战士的能量总和。这很好用树状数组/线段树维护。就我一个 SB 在模拟赛上认为这是可持久化。
容易发现，双方消耗能量永远相同；因此温度为 $t$ 时，消耗总能量为 $2\min(\operatorname{ice}(t),\operatorname{fire}(t))$。
最终答案即求 $\min(\operatorname{ice}(t),\operatorname{fire}(t))$ 最大时，$t$ 的最大值。
根据冰系战士、火系战士的定义，可以发现 $\operatorname{ice}(t)$ 随 $t$ 增大而不降，$\operatorname{fire}(t)$ 随 $t$ 增大而不增。因此 $\min(\operatorname{ice}(t),\operatorname{fire}(t))$ 其实是单峰的（存在取值相同的部分），交点即 $\operatorname{ice}(t)=\operatorname{fire}(t)$ 的点。
普通单峰函数是三分（其实我就写过一次三分），而存在取值相同也不能三分，考虑二分。
二分出一个 $t=t_0$ 使得 $\operatorname{ice}(t)<\operatorname{fire}(t)$ 成立且 $t_0$ 最大。那么最大总能量一定在 $t=t_0$ 或 $t=t_0+1$ 的时候取到。（函数是离散的，可能交点不在整点上，两个点都有可能）。
- 若为 $t=t_0$，则这就是答案，因为 $t$ 再大的时候就不满足总能量最大。
- 若为 $t=t_0+1$ 的时候，还需要再次二分找到 $t=t_0’$ 使得总能量相同，且 $t_0’$ 最大。
温度需要离散化。
这样的复杂度为 $\mathcal O\left(q\log^2q\right)$，考虑道时限 $\text{3s}$，很可以做。
但是据说需要 $\mathcal O(q\log q)$ 的做法，也很简单，就是倍增查询树状数组/线段树二分。直接去掉二分，充分利用已知信息。
AC 代码
懒，$\mathcal O\left(q\log^2q\right)$ 写法。luogu 最慢 $\text{1.83s}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2e6;
struct operation{
int op,t,x,y;
}a[N+1];
int n,len,tmp[N+1];
void discrete(){
for(int i=1;i<=n;i++){
if(a[i].op==1){
tmp[++len]=a[i].x;
}
}
sort(tmp+1,tmp+len+1);
len=unique(tmp+1,tmp+len+1)-tmp-1;
for(int i=1;i<=n;i++){
if(a[i].op==1){
a[i].x=lower_bound(tmp+1,tmp+len+1,a[i].x)-tmp;
}
}
}
struct bit{
int t[N+1+1],sum;
int lowbit(int x){
return x&-x;
}
void add(int x,int k){
sum+=k;
while(x<=N){
t[x]+=k;
x+=lowbit(x);
}
}
int query(int x){
if(x<=0){
return 0;
}
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
}ice,fire;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].op;
switch(a[i].op){
case 1:
cin>>a[i].t>>a[i].x>>a[i].y;
break;
case 2:
cin>>a[i].x;
break;
}
}
discrete();
for(int i=1;i<=n;i++){
if(a[i].op==1){
switch(a[i].t){
case 0:
ice.add(a[i].x,a[i].y);
break;
case 1:
fire.add(a[i].x,a[i].y);
break;
}
}else{
switch(a[a[i].x].t){
case 0:
ice.add(a[a[i].x].x,-a[a[i].x].y);
break;
case 1:
fire.add(a[a[i].x].x,-a[a[i].x].y);
break;
}
}
int l=1,r=len,t=0;
while(l<=r){
int mid=l+r>>1;
if(ice.query(mid)<fire.sum-fire.query(mid-1)){
t=mid;
l=mid+1;
}else{
r=mid-1;
}
}
int ans1=min(ice.query(t),fire.sum-fire.query(t-1));
int ans2=min(ice.query(t+1),fire.sum-fire.query(t));
if(ans1<=0&&ans2<=0){
cout<<"Peace\n";
}else if(ans1>ans2){
cout<<tmp[t]<<' '<<(ans1<<1)<<'\n';
}else{
t++;
int l=t,r=len;
while(l<=r){
int mid=l+r>>1;
if(min(ice.query(mid),fire.sum-fire.query(mid-1))>=ans2){
l=mid+1;
t=mid;
}else{
r=mid-1;
}
}
cout<<tmp[t]<<' '<<(ans2<<1)<<'\n';
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
