知识点:

原题面 Loj Luogu

扯

考场上写了二分 + 树状数组。
没想到可以再二分一次于是加了个 set,水了 60。

当时还不知道线段树上二分这种傻逼玩意= =
今日学到虚脱。

题意简述

简不动,简不动。

分析题意

读完题发现全是废话。可总结出下面几个结论:

1. 将冰火人按温度升序排序,冰人选择的是一段前缀,火人选择的是一段后缀。
   答案即 选择的冰人能量总和 和 火人能量总和 较小的的一方的两倍。
2. 选择的温度一定是某个人的温度。

由结论 2,考虑先离散化温度。

考虑答案的单调性,前缀随温度递增,后缀随温度递减。
答案为前后缀最小的一方,显然为一关于温度的单峰函数。

首先想到二分温度,再用树状数组求得前缀后缀进行检查。
复杂度 \(O(Q\log^2 Q)\),期望得分 \(60pts\)。

发现过不去,考虑科技。

代码实现

//知识点:树状数组上二分 /*By:Luckyblock*/#include <algorithm>#include <cstdio>#include <ctype.h>#include <cstring>#define ll long long#define lowbit(x) (x&-x)const int kMaxn = 2e6 + 10;//=============================================================struct Que {  int opt, t, x, y, k;} q[kMaxn];int data_num, data[kMaxn];int allfire, pos, ans;//=============================================================inline int read() {  int f = 1, w = 0;  char ch = getchar();  for (; !isdigit(ch); ch = getchar())    if (ch == '-') f = -1;  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');  return f * w;}void GetMax(int &fir, int sec) {  if (sec > fir) fir = sec;}void GetMin(int &fir, int sec) {  if (sec < fir) fir = sec;}struct BitTree {  int t[kMaxn];  void Modify(int pos_, int val_) {    for (; pos_ < kMaxn; pos_ += lowbit(pos_)) t[pos_] += val_;  }  int Query(int pos_) {    int ret = 0;    for (; pos_; pos_ -= lowbit(pos_)) ret += t[pos_];    return ret;  }} ice, fire;void Prepare(int Q) {  for (int i = 1; i <= Q; ++ i) {    q[i].opt = read();    if (q[i].opt == 1) {      q[i] = (Que) {q[i].opt, read(), read(), read()};       data[++ data_num] = q[i].x;    } else {      q[i].k = read();     }  }    std :: sort(data + 1, data + data_num + 1);  data_num = std :: unique(data + 1, data + data_num + 1) - data - 1;  for (int i = 1; i <= Q; ++ i) {    if (q[i].opt) q[i].x = std :: lower_bound(data + 1, data + data_num + 1, q[i].x) - data;   }}void Query() {  int len = 0, lsum = 0, rsum = 0;  for (int i = 20; i >= 0; -- i) {    int l = (1 << i);    int newlsum = lsum + ice.t[len + l];    int newrsum = allfire - rsum - fire.t[len + l];    if (len + l <= data_num && newlsum < newrsum) {      len += l;      lsum += ice.t[len],  rsum += fire.t[len];    }  }  int ans1 = std :: min(lsum, allfire - rsum);  int ans2 = std :: min(ice.Query(len + 1), allfire - fire.Query(len));  if (ans1 > ans2) {    pos = len, ans = ans1;    return ;  }  ans = ans2;  len = 0, lsum = 0, rsum = 0;  for (int i = 20; i >= 0; -- i) {    int l = (1 << i);    int newlsum = lsum + ice.t[len + l];    int newrsum = allfire - rsum - fire.t[len + l];    if (len + l <= data_num &&         (newlsum < newrsum || std :: min (newlsum, newrsum) == ans)) {      len += l;      lsum += ice.t[len],  rsum += fire.t[len];    }    pos = len;  }}//=============================================================int main() {  int Q = read();  Prepare(Q);  for (int i = 1; i <= Q; ++ i) {    int opt = q[i].opt, t, x, y, k;    if (opt == 1) {      t = q[i].t, x = q[i].x, y = q[i].y;      if (! t) ice.Modify(x, y);      else fire.Modify(x, y), allfire += y;    } else {      int k = q[i].k;      t = q[k].t, x = q[k].x, y = q[k].y;      if (! t) ice.Modify(x, - y);      else fire.Modify(x, - y), allfire -= y;    }    Query();    if (ans) printf("%d %d\n", data[pos + 1], 2 * ans);    else printf("Peace\n");  }  return 0;}

这里是没写完常数过大过不去就弃了的的线段树二分。
还差一步 找到最大的相等的一段。

#include <algorithm>#include <cstdio>#include <ctype.h>#include <cstring>#include <map>#define ll long long#define ls (lson[now_])#define rs (rson[now_])#define allfire (sum[1][1])const int kMaxn = 2e6 + 10;const int kInf = 2e9;//=============================================================int Q, sumfire, sumice, ans1, ans2, q[kMaxn][3];//0 冰 1 火 int root, node_num, sum[kMaxn << 2][2], lson[kMaxn << 2], rson[kMaxn << 2];std :: map <int, int> fire;//=============================================================inline int read() {  int f = 1, w = 0;  char ch = getchar();  for (; !isdigit(ch); ch = getchar())    if (ch == '-') f = -1;  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');  return f * w;}void GetMax(int &fir, int sec) {  if (sec > fir) fir = sec;}void GetMin(int &fir, int sec) {  if (sec < fir) fir = sec;}void Pushup(int now_) {  sum[now_][0] = sum[ls][0] + sum[rs][0];  sum[now_][1] = sum[ls][1] + sum[rs][1];}void Modify(int &now_, int L_, int R_, int type, int pos_, int val_) {  if (! now_) now_ = ++ node_num;  sum[now_][type] += val_;  if (L_ == R_) return ;  int mid = (L_ + R_) >> 1;  if (pos_ <= mid) Modify(ls, L_, mid, type, pos_, val_);  else Modify(rs, mid + 1, R_, type, pos_, val_);//  Pushup(now_); }int QueryPos(int now_, int L_, int R_, int sum1_, int sum2_) {  if (L_ == R_) return sum1_ + sum[now_][0] <= sum2_ ? L_ : 0;  int mid = (L_ + R_) >> 1, ret = 0;  if (sum1_ + sum[ls][0] < sum2_ - sum[ls][1] + fire[mid]) { //判断 mid 合法性     ret = mid;    GetMax(ret, QueryPos(rs, mid + 1, R_, sum1_ + sum[ls][0], sum2_- sum[ls][1]));   } else {    GetMax(ret, QueryPos(ls, L_, mid, sum1_, sum2_));   }  return ret;}void QuerySum(int now_, int L_, int R_, int pos_) {  int mid = (L_ + R_) >> 1;  if (pos_ < mid) {    QuerySum(ls, L_, mid, pos_);    return ;  }  sumice += sum[ls][0], sumfire -= sum[ls][1];  if (pos_ > mid) QuerySum(rs, mid + 1, R_, pos_);}//=============================================================int main() {  Q = read();  for (int i = 1; i <= Q; ++ i) {    int opt = read(), t, x, y;    if (opt == 1) {      t = q[i][0] = read(), x = q[i][1] = read(), y = q[i][2] = read();      Modify(root, 1, kInf, t, x, y);      if (t) fire[x] += y;    } else {      int k = read();      t = q[k][0], x = q[k][1], y = q[k][2];      Modify(root, 1, kInf, t, x, - y);      if (t) fire[x] -= y;    }    int pos = ans1 = QueryPos(root, 1, kInf, 0, allfire);    sumice = 0, sumfire = allfire + fire[pos];    QuerySum(1, 1, kInf, pos);    ans2 = sumice, sumice = 0, sumfire = allfire + fire[pos + 1];    QuerySum(1, 1, kInf, pos + 1);    if (sumfire >= ans2) {      ans1 = pos + 1, ans2 = sumfire;     }    if (! ans2) printf("Peace\n");    else printf("%d %d\n", ans1, 2 * ans2);  }  return 0;}