P6619 [省选联考 2020 A/B 卷] 冰火战士
大意
给定一个序列，每个数有两种颜色，要找到一个位置，要找到一个位置使得 \(\min \{ f(p), g(p) \}\) 尽可能大.
思路
我们在温度 \(T\) 下，能参加的冰人必须是 \(y \le T\) 的才能参赛，火人必须是 \(y \ge T\) 才能参赛，我们定义能参赛的冰人的能量和为 \(f(T)\)，同理，火人为 \(g(T)\)。
那么我们的答案一定是 \(2 \times \min \{ f(T), g(T)\}\)，对于这个图，画出来是下面这样的：
那么，取 \(\min\) 之后的图像是这样的：
就是绿色的部分，那么我们这样的话，答案一定在交点附近，那么我们在求这个交点的过程，可以尝试二分 + 树状数组，由于一个是递增，一个是递减，分别维护前缀和和后缀和即可，那么这样二分到交点 \(p\) 的话，只需要看 \(p\) 和 \(p + 1\) 位置，相当于是冰人和火人的位置，火人的位置比较特殊，因为是可能后面还有段连续的区间，需要继续从 \(p + 1\) 向右跳到最后一个合法的区间。
而上述的做法，不难发现时间复杂度是 \(Q \log^2 Q\) 的，无法通过此题，只能有 \(60pts\)，于是我们考虑优化。
有个比较经典的思路（不过我也是刚学会的），在树状数组上倍增，这样的话，我们只需要单 \(\log\) 的复杂度去跳交点，以及查找 \(p + 1\) 的后面最后一个满足情况的点即可。
代码
#include<bits/stdc++.h>
using namespace std;#define ll long long
const int MAXN = 2 * 1e6 + 5;
ll t1[MAXN], t2[MAXN];
int lsh[MAXN], tot;
ll sum = 0;struct node{int op, t, x, y;
}q[MAXN];int lowbit(int x){return x & -x;
}void add(ll *bit, int x, ll k){
// if(x <= 0) return;while(x <= tot + 1){bit[x] += k;x += lowbit(x);}
}int Q;int main(){cin.tie(0) -> ios::sync_with_stdio(0);cin >> Q;for(int i = 1;i <= Q;i ++){cin >> q[i].op;if(q[i].op == 1){cin >> q[i].t >> q[i].x >> q[i].y;lsh[++ tot] = q[i].x;}else{cin >> q[i].t;}}sort(lsh + 1, lsh + tot + 1);tot = unique(lsh + 1, lsh + tot + 1) - (lsh + 1);for(int i = 1;i <= Q;i ++){if(q[i].op == 1){q[i].x = lower_bound(lsh + 1, lsh + tot + 1, q[i].x) - lsh;}}for(int i = 1;i <= Q;i ++){if(q[i].op == 1){if(q[i].t == 0) add(t1, q[i].x, q[i].y);else add(t2, q[i].x + 1, q[i].y), sum += q[i].y;}else{if(q[q[i].t].t == 0) add(t1, q[q[i].t].x, -q[q[i].t].y);else add(t2, q[q[i].t].x + 1, -q[q[i].t].y), sum -= q[q[i].t].y;}ll p1 = 0, s1 = 0, s2 = 0;for(int j = 20;j >= 0;j --){int nxt = p1 + (1 << j);if(nxt <= tot && s1 + t1[nxt] < sum - (s2 + t2[nxt])){p1 = nxt, s1 += t1[nxt], s2 += t2[nxt];}}ll res1 = s1;ll res2 = 0, p2 = 0;if(p1 < tot){ll ss1 = 0, ss2 = 0;for(int j = p1 + 1;j;j -= lowbit(j)){ss1 += t1[j], ss2 += t2[j];}res2 = sum - ss2;if(res2 >= res1){p2 = 0, ss2 = 0;for(int j = 20;j >= 0;j --){int nxt = p2 + (1 << j);if(nxt <= tot && sum - (ss2 + t2[nxt]) >= res2){p2 = nxt;ss2 += t2[nxt];}}}}if(res1 == res2 && res1 == 0){cout << "Peace\n";}else if(res1 <= res2){cout << lsh[p2] << ' ' << res2 * 2 << '\n';}else{cout << lsh[p1] << ' ' << res1 * 2 << '\n';}}return 0;
}