Legend
维护两个二元组集合 \(A,B\)，支持操作 \(Q\ (1 \le Q \le 2\times10^6)\) 次：
- 向其中某个集合插入一个二元组 \((t,e) \ (1 \le t \le 2\times 10^9,\sum e \le 2 \times 10^9)\)。
- 删除之前插入的一个二元组。
每次操作后都会询问：
-
对于给定的 \(mid\) ，定义 \(Ans=\min\left(\sum\limits _{a\in A}[a.t\le mid]\times a.e,\sum\limits_{b\in B} [b.t \ge mid]\times b.e\right)\)。
-
请给出能取到最大的 \(Ans\times 2\) 的值 ，以及取到最大 \(Ans\) 时的最大 \(mid\)。
时空 \(\textrm{3s/512MB}\)。
Editorial
作为 联合省选\(2020\) 的第一题，必定是一道良心送温暖题，但大力的卡常似乎让它失去了应有的效果，让我们一起为出题人点踩。
wrong answer
我们把集合 \(A\) 里的二元组 \((t,e)\) 看成对一个数组 \(a\) 执行 \(a_t\gets a_t+e\)。
我们把集合 \(B\) 里的二元组 \((t,e)\) 看成对一个数组 \(b\) 执行 \(b_t\gets b_t+e\)。
因为不强制在线，显然可以先把 \(t\) 离散化到 \(O(Q)\) 级别。
那么题目实际上就是让我们取得数组 \(a\) 的一个前缀和 \(Sa\)，\(b\) 的一个后缀和 \(Sb\)，满足 \(a\) 最后一个数的下标小于等于 \(b\) 第一个数的下标，使得 \(\min(Sa,Sb)\) 尽可能大，在此前提下 \(mid\) 尽量大。
容易想到这个东西关于 \(mid\) 是个凸函数，我们尝试去三分最终温度。
可惜的是值域不是连续的，整数域上难以三分。
模拟退火，我觉得它过不了 \(\textrm{2e6}\) 的询问。
binary to ternary
先不考虑 \(mid\) 的计算，只考虑 \(Ans\)。
考虑把三分变成二分，考虑到只有两个数组，发现 \(Ans\) 最大时一定满足这二者之一：
- \(Sa\le Sb\)，且 \(Sa\) 尽可能大。
- \(Sa\ge Sb\)，且 \(Sb\) 尽可能大。
这两种情况是可以直接二分的。
直接二分，还要维护前后缀和，复杂度 \(O(Q \log^2 Q)\)。
改为使用线段树二分，复杂度 \(O(Q \log Q)\)。
calculating \(mid\)
线段树二分我们可以顺带找到对应取得最大值的位置 \(mid'\)，但它不一定是最大的那个。
对于 “\(Sa\le Sb\)，且 \(Sa\) 尽可能大” 的情况，线段树二分的确可以直接满足 \(mid'=mid\)，可以直接输出。
但对于第二类 “\(Sa\ge Sb\)，且 \(Sb\) 尽可能大” 的情况，我们则需要找到 \(\ge mid'\) 的第一个 \(i\) 使得 \(b_i\not = 0\)。此时 \(mid=i\)。 这可以直接使用一个 \(\textrm{multiset}\) 实现。
Code
细节不是很多，常数却有很大。
在 \(\textrm{LOJ}\) 压时限过，在 \(\textrm{luogu}\) 怕是人没了。
Author : Imakf
#include <bits/stdc++.h>
#define LL long long
const int MX = 2e6 + 23;
using namespace std;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9')
x = x * 10 + k - '0' ,k = getchar();
return x;
}
struct Operation{
int type ,t ,x ,y ,k ,id;
void readSign(){type = 1 ,t = read() ,x = read() ,y = read();}
void readWithdraw(){type = 2 ,k = read();}
bool operator <(const Operation &B)const{return x < B.x;}
}O[MX];
bool cmp(Operation A ,Operation B){return A.id < B.id;}
struct node{
int l ,r ,s[2];
node *lch ,*rch;
}*root;
void pushup(node *x){
x->s[0] = x->lch->s[0] + x->rch->s[0];
x->s[1] = x->lch->s[1] + x->rch->s[1];
}
node *build(int l ,int r){
node *x = new node; x->l = l ,x->r = r ,x->s[0] = x->s[1] = 0;
if(l == r) x->lch = x->rch = nullptr;
else{int mid = (l + r) >> 1;
x->lch = build(l ,mid);
x->rch = build(mid + 1 ,r);
pushup(x);
}return x;
}
void add(node *x ,int p ,int belong ,int v){
if(x->l == x->r) return x->s[belong] += v ,void();
if(p <= x->lch->r) add(x->lch ,p ,belong ,v);
else add(x->rch ,p ,belong ,v);
return pushup(x);
}
#define pi pair<int ,int>
#define mp make_pair
bool operator <(pi a ,pi b){
return a.first == b.first ? a.second < b.second : a.first < b.first;
}
pi max(pi a ,pi b){return a < b ? b : a;}
pi qsmall(node *x ,int lsum = 0 ,int rsum = 0){ // ice <= fire 的最后一个位置
if(x->l == x->r) return mp(min(lsum + x->s[0] ,rsum + x->s[1]) ,x->l);
int nlsum = lsum + x->lch->s[0] ,nrsum = rsum + x->rch->s[1];
if(nlsum <= nrsum) return qsmall(x->rch ,nlsum ,rsum);
return qsmall(x->lch ,lsum ,nrsum);
}
pi qbig(node *x ,int lsum = 0 ,int rsum = 0){ // ice >= fire 的第一个位置
if(x->l == x->r) return mp(min(lsum + x->s[0] ,rsum + x->s[1]) ,x->l);
int nlsum = lsum + x->lch->s[0] ,nrsum = rsum + x->rch->s[1];
if(nlsum >= nrsum) return qbig(x->lch ,lsum ,nrsum);
return qbig(x->rch ,nlsum ,rsum);
}
int lsh[MX] ,lshcnt;
int main(){
int Q = read();
for(int i = 1 ,op ; i <= Q ; ++i){
op = read();
if(op == 1) O[i].readSign();
else O[i].readWithdraw();
O[i].id = i;
}
sort(O + 1 ,O + 1 + Q);
int lastx = -1;
for(int i = 1 ; i <= Q ; ++i){
if(O[i].type == 2) continue;
if(O[i].x != lastx) lsh[++lshcnt] = O[i].x;
lastx = O[i].x ,O[i].x = lshcnt;
}
sort(O + 1 ,O + 1 + Q ,cmp);
root = build(1 ,lshcnt);
multiset<int> soldier;
soldier.insert(MX);
for(int i = 1 ; i <= Q ; ++i){
int p = i;
if(O[p].type == 1){
/*
printf("Add type = \"%s\" ,temperature = %d ,energy = %d\n"
,O[p].t ? "fire" : "ice"
,O[p].x
,O[p].y);
*/
add(root ,O[p].x ,O[p].t ,O[p].y);
if(O[p].t) soldier.insert(O[p].x);
}
else{
p = O[p].k;
add(root ,O[p].x ,O[p].t ,-O[p].y);
if(O[p].t) soldier.erase(soldier.find(O[p].x));
}
pi vbig = qbig(root) ,vsm = qsmall(root);
pi v = max(vbig ,vsm);
// printf("Tmp pos = %d\n" ,lsh[v.second]);
if(!v.first){
puts("Peace");
continue;
}
if(v.first == vsm.first && v.first != vbig.first){
printf("%d %d\n" ,lsh[v.second] ,v.first * 2);
continue;
}
int pos = *soldier.lower_bound(v.second);
if(v.first) printf("%d %d\n" ,lsh[pos] ,v.first * 2);
}
return 0;
}