前言
真正的宝石纵使无光，亦能闪耀。
今天的纯唐氏题目我居然不会做。
考试的时候脑子跟生锈了一样。
考虑到 \(1,2\) 题都太一眼了，这里就只总结一下最后两道题。
多重集
这道题目的重点是去观察对于 \(a_x,b_x,a_y,b_y\) 什么条件下 \(a_x+a_y\) 更小，以及什么条件下 \(b_x+b_y\) 更小。
其实判定条件是多种多样的，我这里写一种比较简洁的，跟题解是一样的，但是跟我考试的时候推出来的柿子不太一样（其实两者都可以做）的判定条件：
-
定义 \(h_x=a_x-b_x(x\in A),h_y=b_y-a_y(y\in B)\)
-
显然，稍微写一下式子就可以得到，当 \(h_x\le h_y,\min=b_x+b_y\)。反之亦然。
故我们考虑以 \(h_x\) 为下标开一颗权值线段树，在合并的时候，左儿子和右儿子本身就满足 \(h\) 的偏序关系，所以你就可以大胆将合并，只需要维护 \(A,B\) 集合 \(h\) 在这个区间中 \(a,b\) 的最小值即可。然后合并的时候维护答案。
观察到有 \(n\le 10^6\)，故你还是考虑一个离散化防止出事，然后注意到有可能 \(h_x\) 对于不同的 \(x\) 可能会相同，故你要对权值线段树的叶子节点要开一个 \(\texttt{multiset}\)，只向上传有用的就行了。
也不知道考试发生了什么，前面的都想到了，但是一直在想将 \(A,B\) 分别开一颗独立的线段树，然后看怎么合并统计答案，却忘了线段树上本质上是有偏序条件的啊啊啊啊啊。
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000005
int q;
int op1[maxn], op2[maxn], x[maxn], y[maxn];
int ls[maxn], lslen;
struct segmentree
{
int l, r;
long long data[4], ans;//min(a,b) max(a,b)
}tree[maxn << 2];
multiset<long long> s[maxn][4];
void build(int p, int l, int r)
{
tree[p].l = l, tree[p].r = r;
tree[p].ans = 2e9;
for (int i = 0; i < 4; ++i) tree[p].data[i] = 2e9;
if(l == r) return;
int mid = (l + r) >> 1;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
}
void change(int p, int x, int y)
{
if(tree[p].l > x || tree[p].r < x) return;
if(tree[p].l == tree[p].r)
{
int d = op2[y] ? 2 : 0, l = tree[p].l;
if(op1[y])
{
s[l][d].insert(::x[y]);
s[l][d + 1].insert(::y[y]);
}
else
{
s[l][d].erase(s[l][d].find(::x[y]));
s[l][d + 1].erase(s[l][d + 1].find(::y[y]));
}
tree[p].ans = 2e9;
if(s[l][0].size() && s[l][2].size()) tree[p].ans = (*s[l][0].begin()) + (*s[l][2].begin());
if(s[l][1].size() && s[l][3].size()) tree[p].ans = min((*s[l][1].begin()) + (*s[l][3].begin()), tree[p].ans);
for (int i = 0; i < 4; ++i) tree[p].data[i] = s[l][i].size() ? (*s[l][i].begin()) : 2e9;
return;
}
change(p << 1, x, y), change(p << 1 | 1, x, y);
for (int i = 0; i < 4; ++i) tree[p].data[i] = min(tree[p << 1].data[i], tree[p << 1 | 1].data[i]);
tree[p].ans = min(tree[p << 1].ans, tree[p << 1 | 1].ans);
tree[p].ans = min(tree[p << 1].data[2] + tree[p << 1 | 1].data[0], tree[p].ans);
tree[p].ans = min(tree[p << 1].data[1] + tree[p << 1 | 1].data[3], tree[p].ans);
}
int main()
{
scanf("%d", &q);
for (int i = 1; i <= q; ++i) scanf("%d %d %d %d", &op1[i], &op2[i], &x[i], &y[i]), ls[++lslen] = (op2[i] ? y[i] - x[i] : x[i] - y[i]);
stable_sort(ls + 1, ls + lslen + 1), lslen = unique(ls + 1, ls + lslen + 1) - ls - 1;
build(1, 1, lslen);
for (int i = 1; i <= q; ++i)
{
int h = (op2[i] ? y[i] - x[i] : x[i] - y[i]);
h = lower_bound(ls + 1, ls + lslen + 1, h) - ls;
change(1, h, i);
if(tree[1].ans >= 2e9) puts("-1");
else printf("%lld\n", tree[1].ans);
}
return 0;
}