Luogu P6619 「省选联考 2020 A/B 卷」 冰火战士「树状数组二分」

P6619 [省选联考 2020 A/B 卷] 冰火战士

简化题意：

冰战士、火战士组成冰火两队，每个战士有温度 (x) 和能量 (y) 两个属性。若选择场地温度 (T)，则冰队温度 (leq T) 的战士参赛，火队温度 (geq T) 的战士参加，设冰队、火队参加战士的能量和是 (a,b)，你要选择 (T) 来最大化 (2cdot min(a,b))，若有多个 (T) 选择较大的。现有 (Q) 条信息，加入战士或者撤回战士，请你再每次信息后输出 (T) 和 (2cdot min(a,b))，若这个值为 (0) 输出 Peace。

(Q leq 2cdot 10^6,1leq xleq 2cdot 10^9,sum y leq 2cdot 10^9)，同队所有战士均不同。

题解：树状数组二分

场上线段树二分都卡 TLE 了吧（zkw 除外），看来要学习小常数做法。

容易发现 (T) 变大时，冰队能量和 (a) 在增大，火队能量和 (b) 在减小，所以找到 (aleq b) 时最大的 (T) 和 (a> b) 时 (b) 最大的 (T)（尽量选 (T) 大的）。

考场上脑抽浪费了不少时间，我以为温度可以不是某个战士的温度，还用了 multiset 啥的。其实直接离散化，只考虑离散化的温度就行。为了方便把火队离散化后温度的 (x) 都加一，这样参赛的战士是冰队温度 (leq T) 和火队温度 (>T) 的。我们用两个树状数组，分别记录两个队的能量。那每次我们从高位往低位枚举 (k)，看当前温度 (t) 能否加上 (2^k)，([t + 1, t+2^k]) 的答案恰就存储在树状数组 (t + 2^k) 的位置，直接判断即可。

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
char gc() {
   static char buf[1 << 17], *S, *T;
   if(S == T) T = (S = buf) + fread(buf, 1, 1 << 17, stdin);
   return S == T ? EOF : *S ++;
}
template<class T> void read(T &x) {
   x = 0; char c = gc(); bool na = 0;
   for(; c < '0' || c > '9'; c = gc()) na |= c == '-';
   for(; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c & 15);
   if(na) x = -x;
}
const int N = 2e6 + 10;
struct node {
   int op, t, x, y;
} a[N];
int w[N], n, logn;
struct BIT {
   int bit[N], arr[N], sum;
   void add(int u, int v) {
      sum += v; arr[u] += v;
      for(; u <= n; u += u & (-u)) bit[u] += v;
   }
   int qry(int u) {
      int ans = 0;
      for(; u >= 1; u &= u - 1) ans += bit[u];
      return ans;
   }
} b[2];
int main() {
   int q; read(q);
   rep(i, 1, q) {
      read(a[i].op); read(a[i].t);
      if(a[i].op == 1) {
         read(a[i].x); read(a[i].y);
         w[++ *w] = a[i].x;
      }
   }
   sort(w + 1, w + *w + 1);
   n = unique(w + 1, w + *w + 1) - w;
   for(logn = 0; (1 << (logn + 1)) <= n; logn ++) ;
   rep(i, 1, q) if(a[i].op == 1) a[i].x = lower_bound(w + 1, w + n, a[i].x) - w + a[i].t;
   rep(i, 1, q) {
      if(a[i].op == 1) {
         b[a[i].t].add(a[i].x, a[i].y);
      } else {
         int id = a[i].t;
         b[a[id].t].add(a[id].x, - a[id].y);
      }
      int s0 = 0, s1 = b[1].sum, t = 0;
      per(k, logn, 0) if(t + (1 << k) <= n) {
         if(s0 + b[0].bit[t + (1 << k)] <= s1 - b[1].bit[t + (1 << k)]) {
            t += 1 << k; s0 += b[0].bit[t]; s1 -= b[1].bit[t];
         }
      }
      int ans = s0, a2 = s1 - b[1].arr[t + 1];
      if(a2 >= ans) {
         ans = a2; t = 0; s1 = b[1].sum;
         per(k, logn, 0) if(t + (1 << k) <= n) {
            if(s1 - b[1].bit[t + (1 << k)] >= ans) {
               t += 1 << k; s1 -= b[1].bit[t];
            }
         }
      }
      if(ans == 0) puts("Peace");
      else printf("%d %d
", w[t], ans * 2);
   }
   return 0;
}