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 LOCALfreopen("in.txt","r",stdin);freopen("my.out","w",stdout);#elsefreopen("set.in","r",stdin);freopen("set.out","w",stdout);#endifread(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');}
}
