考场上写了二分 + 树状数组。
没想到可以再二分一次于是加了个 set，水了 60。
当时还不知道线段树上二分这种傻逼玩意= =
今日学到虚脱。
简不动，简不动。
读完题发现全是废话。可总结出下面几个结论：
由结论 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;
}
原文：https://www.cnblogs.com/luckyblock/p/13562402.html