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

· · 题解

注意到一旦双方出战名单确定，无论出战顺序如何，因为双方耗费的能量一定相同，且至少有一方能量耗尽时才能结束，因此答案是两队能量和最小值的两倍。

同时我们注意到一个性质：冰系战士的能量总和随温度升高而递增（本质上是一个前缀和），火系战士的能量总和随温度身高而下降（本质上是一个后缀和），因此如果我们把每个温度下消耗的能量标出来，答案是一个单峰曲线。

当然有两个问题：

  1. 温度是离散的，因此曲线本质上也是离散的。这意味着我们可能找不到冰系战士能量和以及火系战士能量和曲线的交点；
  2. 因为存在答案不变的段，三分显然不行。

不过我们还是能想到一个还算不错的算法：我们通过二分的方式来找两条曲线的交点。具体来说，我们找到使得冰系战士能量（记为 f(k)）小于火系战士能量（记为 g(k)）的最高温度 k，则一定有 f(k+1) \geq g(k+1)，这时候我们再找到一个最大的 k'，使得 g(k+1)=g(k')。

此时，最终答案必将在 k 和 k' 二者中取得其一，具体是哪一个取决于相应温度下能量消耗值的相对大小。

整个过程我们需要二分+树状数组（要查前后缀和）来实现，时间复杂度 O(n \log^2 n)，可以拿到 60 分。

考虑优化上面这个过程。树状数组肯定是没法省掉了，能不能不二分呢？答案是肯定的。

具体来说，我们采用了一种直接在树状数组上二分（倍增）的做法。这种方法的实质是利用之前计算过的信息，避免了重复计算。

假如我们现在在 p 位置，我们不停尝试向前跳，跳的步长依次递减，为 2^{20},2^{19},2^{18},\ldots,2^0，如何判断 p+d 这个位置满足要求呢？我们不用再重新计算 p+d 的前缀（后缀）和，而是直接将树状数组上 p+d 位置的信息累加到总和中即可。

熟悉树状数组的同学应该清楚，因为我们从高位向低位依此考虑，p+d 这个位置刚好存储了 [p+1,p+d] 这个区间内的所有信息，因此这样直接累加的做法是正确的。

剩下的就和原来 60 分的做法差不多了。

// Problem : P6619 [省选联考 2020 A/B 卷] 冰火战士
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P6619
// Memory Limit : 512 MB
// Time Limit : 3000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <algorithm>
#include <iostream>
using namespace std;
struct query {
  int op;
  int k;
  int t, x, y;
} a[2000005];
struct BIT {
  long long a[2000005];
  int n;
  void init(int x) { n = x; }
  int lowbit(int x) { return x & (-x); }
  void add(int x, int y) {
    while (x <= n) a[x] += y, x += lowbit(x);
  }
  long long query(int x) {
    long long ans = 0;
    while (x) ans += a[x], x -= lowbit(x);
    return ans;
  }
  long long get(int x) { return a[x]; }
} tr0, tr1;
long long sum1;
int p[2000005], cnt;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].op;
    if (a[i].op == 1) {
      cin >> a[i].t >> a[i].x >> a[i].y;
      p[++cnt] = a[i].x;
    } else
      cin >> a[i].k;
  }
  sort(p + 1, p + cnt + 1);
  cnt = unique(p + 1, p + cnt + 1) - p - 1;
  for (int i = 1; i <= n; i++)
    if (a[i].op == 1) a[i].x = lower_bound(p + 1, p + cnt + 1, a[i].x) - p;
  tr0.init(cnt), tr1.init(cnt);
  for (int i = 1; i <= n; i++) {
    if (a[i].op == 1) {
      if (!a[i].t)
        tr0.add(a[i].x, a[i].y);
      else
        tr1.add(a[i].x + 1, a[i].y), sum1 += a[i].y;
    } else {
      int k = a[i].k;
      if (!a[k].t)
        tr0.add(a[k].x, -a[k].y);
      else
        tr1.add(a[k].x + 1, -a[k].y), sum1 -= a[k].y;
    }
    long long s0 = 0, s1 = sum1;
    long long f1 = 0, f2 = 0;
    int p1 = 0, p2 = 0;
    for (int i = 20; i >= 0; i--) {
      int np = p1 + (1 << i), ns0 = s0 + tr0.get(np), ns1 = s1 - tr1.get(np);
      if (np > cnt) continue;
      if (ns0 < ns1) {
        p1 = np;
        s0 = ns0, s1 = ns1;
      }
    }
    f1 = s0, s0 = 0, s1 = sum1;
    if (p1 < cnt) {
      f2 = min(tr0.query(p1 + 1), sum1 - tr1.query(p1 + 1));
      for (int i = 20; i >= 0; i--) {
        int np = p2 + (1 << i), ns0 = s0 + tr0.get(np), ns1 = s1 - tr1.get(np);
        if (np > cnt) continue;
        if (ns0 < ns1) {
          p2 = np;
          s0 = ns0, s1 = ns1;
        } else if (min(ns0, ns1) == f2) {
          p2 = np;
          s0 = ns0, s1 = ns1;
        }
      }
    }
    if (max(f1, f2) == 0)
      cout << "Peace" << endl;
    else if (f1 > f2)
      cout << p[p1] << ' ' << f1 * 2 << endl;
    else
      cout << p[p2] << ' ' << f2 * 2 << endl;
  }
  return 0;
}