RT 样例没过

权值树状数组上倍增

存火人温度的时候直接存在了 +1 位置方便查询

rnk 去重之后的温度排名
p 离散化用了，离散化完之后改成了根据排名查找温度的索引

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 2e6 + 10;

template <typename Temp> inline void read(Temp & res) {
	Temp fh = 1; res = 0; char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
	for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
	res = res * fh;
}

int n, cnt, m, opt[Maxn], d[Maxn], t[Maxn], p[Maxn], rnk[Maxn], at[Maxn];
LL e[Maxn], sf;
bool cmp(int A, int B) {return t[A] < t[B];}

struct BIT {
	LL Array[Maxn];
	void add(int t, LL d) {
		while(t <= m) {
			Array[t] += d;
			t += (-t&t);
		}
	}
	LL sum(int t) {
		LL res = 0;
		while(t) {
			res += Array[t];
			t -= (-t&t);
		}
		return res;
	}
	LL query(int l, int r) {
		return sum(r) - sum(l - 1);
	}
};
BIT I, F;

void solve() {
	int p1 = 0, p2 = 0;
	LL s1 = 0, s2 = sf;
	for(int b = 21; b >= 0; --b) {
		int to = p1 + (1 << b);
		if(to > m) continue;
		LL ts1 = s1 + I.Array[to], ts2 = s2 - F.Array[to];
		if(ts1 < ts2)
			p1 = to, s1 = ts1, s2 = ts2;
	}
	LL wi = s1, wf = 0; s1 = 0, s2 = sf;
	if(p1 < m) {
		wf = min(I.query(1, p1 + 1), F.query(p1 + 1, m));
		for(int b = 21; b >= 0; --b) {
			int to = p2 + (1 << b);
			if(to > m) continue;
			LL ts1 = s1 + I.Array[to], ts2 = s2 - F.Array[to];
			if(ts1 < ts2 || ts2 == wf)
				p2 = to, s1 = ts1, s2 = ts2;
		}
	}
	if(min(wi, wf) <= 0) printf("Peace\n");
	else if(wi < wf) printf("%d %lld\n", p[p1], wi << 1);
	else printf("%d %lld\n", p[p2], wf << 1);
}

int main() {
	read(n);
	for(int i = 1; i <= n; ++i) {
		read(opt[i]);
		if(opt[i] == 1)
			read(d[i]), read(t[i]),
			read(e[i]), p[++cnt] = i;
		else
			read(d[i]);
	}
	
	sort(p + 1, p + cnt + 1, cmp);
	for(int i = 1; i <= cnt; ++i)
		rnk[p[i]] = t[p[i]] == t[p[i - 1]] ? m : ++m;
	for(int i = 1; i <= n; ++i) if(opt[i] == 1) p[rnk[i]] = t[i];
	
	for(int i = 1; i <= n; ++i) {
		if(opt[i] == 1)
			if(d[i] == 0) I.add(rnk[i], e[i]);
			else F.add(rnk[i] + 1, e[i]), sf += e[i];
		else
			if(d[d[i]] == 0) I.add(rnk[d[i]], -e[d[i]]);
			else F.add(rnk[d[i]] + 1, -e[d[i]]), sf -= e[d[i]];
		solve();
	}
	
	return 0;
}