BC2402C. 多重集（set）
题意
给你两个集合 \(A,B\)，开始时集合为空。有 \(n\) 次操作，每次往其中一个集合插入或者删除一个数对 \((a,b)\)，保证删除的数对存在。每次操作后输出 \(\min_{x,y} \{ \max(a_x+a_y,b_x+b_y),(a_x,b_x)\in A,(a_y,b_y) \in B \}\)。
思路
一个显然的优化是按照 \(a_x+a_y,b_x+b_y\) 的大小关系分类讨论，以此去除讨厌的 \(\max\)。
当 \(a_x+a_y \ge b_x+b_y\) 时，有 \(a_x-b_x \ge -a_y + b_y\)。因此我们可以对于每一个 \(x\)，对于满足 \(a_x-b_x \ge -a_y + b_y\) 的 \(y\)，取 \(\max\) 一定会取到 \(a_x+a+y\)，因此对这些 \(y\) 求 \(a\) 的最小值。对于 \(a_x-b_x < -a_y + b_y\) 的 \(y\) 同理，求 \(b\) 的最小值。
只考虑插入操作，可以将操作离线，以 \(a_i-b_i\) 对离散化后的操作排序，相当于前缀或者后缀求最小值，以及动态插入，用线段树可以维护。
然后愚蠢的我以为求最小值不支持删除操作。大概是被莫队搞晕了。线段树本来就是支持单点甚至区间修改维护最大值和最小值的。
因此删除操作就单点删除，然后上传更新最小值即可。
时间复杂度是 \(O(n \log n)\)。主要难点在于想到对 \(\max\) 进行分类讨论（需要做题经验显然我好不容易有了然后脑抽）以及不要脑抽。
一种比较优美的写法是，首先线段树节点肯定要存 \(a,b\) 最小值，把两个集合的信息一个集合以 \(a_i-b_i\) 排名为下标，另一个以 \(-a_i+b_i\) 排名为下标，存在一棵树里，在线段树里维护答案。
code
感觉减少常数需要精细思考，但是代码还是很好写的。
#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x++)
using namespace std;
typedef long long ll;
constexpr int N=1e6+7;
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
void read(T &x) {
x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) ;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
template <typename T>
void write(T x,char ch) {
static int st[20];
int top=0;
do {
st[top++]=x%10;
x/=10;
}while(x);
while(top) putchar(st[--top]+'0');
putchar(ch);
}
int q;
int cnt;
typedef unsigned int uint;
constexpr uint inf=0x7f7f7f7f;
struct pii {
uint a,b;
bool operator < (const pii x) const { return a!=x.a?a<x.a:b<x.b; }
};
struct node {
int d;
pii x;
bool operator < (const node y) const {
int c1=d?x.b-x.a:x.a-x.b,c2=y.d?y.x.b-y.x.a:y.x.a-y.x.b;
return c1!=c2 ? c1<c2 : (d!=y.d?d<y.d:x<y.x) ;
}
}t[N];
struct que{
int op,d;
pii x;
}qu[N];
int op,d,a,b;
struct tree {
pii mn[N<<2][2]; uint tr[N<<2];
tree() { memset(mn,0x7f,sizeof(mn)); memset(tr,0x7f,sizeof(tr)); }
pii _min(pii x,pii y) { return {min(x.a,y.a),min(x.b,y.b)}; }
void pushup(int u) {
mn[u][0]=_min(mn[u<<1][0],mn[u<<1|1][0]); mn[u][1]=_min(mn[u<<1][1],mn[u<<1|1][1]);
tr[u]=min(min(tr[u<<1],tr[u<<1|1]),min(mn[u<<1][1].a+mn[u<<1|1][0].a,mn[u<<1][0].b+mn[u<<1|1][1].b));
}
void insert(int u,int l,int r,int x,int del) {
if(l==r) {
if(del) memset(mn[u],0x7f,sizeof(mn[u])), tr[u]=inf;
else mn[u][t[x].d]=t[x].x;
return;
}
int mid=(l+r)>>1;
if(x<=mid) insert(u<<1,l,mid,x,del);
else insert(u<<1|1,mid+1,r,x,del);
pushup(u);
}
}T;
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#else
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
#endif
read(q);
rep(i,1,q) {
read(op),read(d),read(a),read(b);
qu[i]={op,d,{a,b}};
if(op) t[++cnt]={d,{a,b}};
}
sort(t+1,t+cnt+1);
rep(i,1,q) {
int op=qu[i].op,d=qu[i].d;
pii x=qu[i].x;
int pos=lower_bound(t+1,t+cnt+1,(node){d,x})-t;
T.insert(1,1,cnt,pos,op==0);
uint ans=T.tr[1];
if(ans==inf) puts("-1");
else write(ans,'\n');
}
}