小知识：VSCode 通过调整 Editor: Cursor Surrounding Lines 可以达到 Typora 打字机模式的效果。调到任意一个超过屏幕总行数的值可以让焦点居中。很舒服。
T1 move
http://222.180.160.110:1024/contest/5006/problem/1
注意到 \(x\) 和 \(y\) 的绝对值是分开计算的，只用分类讨论 \(x\) 和 \(y\) 最终正负性的四种情况，取最大答案即可。
T2 bicoloring
http://222.180.160.110:1024/contest/5006/problem/2
bi 这个前缀是二的意思，比方说 binary 等等。
简单 DP，为了好写直接把每一列的四种颜色情况加到状态里，枚举连通块数对一个选择的新增连通块数进行转移即可。值得注意的是 DP 数组的连通块数量维需要开两倍。
T3 express
http://222.180.160.110:1024/contest/5006/problem/3
想不出来这个标题和星际货运四个字有什么联系。
假如只有一维，那么显然按坐标排序相邻的两个之间连边。
现在有三维，那么就把三个坐标分开排序，然后带选的 \(3\times (n-1)\) 条边全部拿来 Kruskal 就好。
T4 round
http://222.180.160.110:1024/contest/5006/problem/4
袁术（不是
裸数位 DP，但是要注意前导 0 不能统计到 0 的数量里，记忆化数组也要加一维记录前导 0 状态。
T5 string
http://222.180.160.110:1024/contest/5006/problem/5
注意到这是一个可以用哈希拿到 40pts 的 AC 自动机。
T6 letter
http://222.180.160.110:1024/contest/5006/problem/6
注意到暴力有 60pts。
T1 gamble
http://222.180.160.110:1024/contest/5001/problem/1
假设 钦定 当前我方摇出来的数值是 \(p\)，对面的硬币两面分别是 \(a,b(a\le b)\)，赌注是 \(x\)。那么分三种情况：
- \(p < a\)，期望收益为 \(-x\)；
- \(p\in [a, b)\)，期望收益为 \(0\)；
- \(p \ge b\)，期望收益为 \(x\)。
也就是说如果我们选择让硬币的两面成为 \(p,q\)，期望收益应为 \(\dfrac {E_p+E_q}2 - p\times q\)。乘上 4 就是 \(2\times (E_p + E_q) - 4\times p \times q\)。
注意到 \(p,q\) 的值一定在所有 \(a, b\) 中出现过，故可离散化 \(a,b\) 求出每个 \(E_i\)，枚举 \(p\) 并求得相应 \(q\)。
\(E_i\) 的具体求法就是对于每一对 \(a, b\)，把三个对应区间修改一下，因为是离线的所以差分什么的都没问题。
注意到令 \(k=-4\times q\) 且 \(b = E_q\) 后问题转变为 \(x=p\) 上的最高交点问题，可以李超。因为值域很大，所以需要动态开点。
因为把 \(a\) 和 \(b\) 一起离散了，所以数组都要两倍。
以及为了防止可能出现的意外要向 \(p, q\) 可选值里先丢一个最小值 \(1\) 用来应对怎么选都亏不如摆烂的情况。
比较神奇的是大常数 \(\mathcal O(n\log^2)\) 跑 2s 的 1e6 居然没有问题。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int lim = 1e9;
const int inf = 1e18;
const int maxn = 5e5 + 5;
const int maxm = 1e6 + 5;
#define lt t[p].l
#define rt t[p].r
int a[maxm], b[maxm];
int n, cnt, res, tot, r, now;
struct { int k, b; } seg[maxm];
struct { int a, b, x; } v[maxn];
struct _ { int l, r, u; } t[maxm << 2];
int max(int x, int y) { return x > y ? x : y; }
void swap(int &x, int &y) { x ^= y ^= x ^= y; }
int getup(int j, int k) { return a[j] - a[k]; }
int getdown(int j, int k) { return b[j] - b[k]; }
int getDP(int i, int j) { return a[i] + a[j] - b[i] * b[j]; }
int getv(int id, int x) {
if (!id) return -inf;
return x * seg[id].k + seg[id].b;
}
void upd(int &p, int lv, int rv, int id) {
if (!p) p = ++now;
if (!t[p].u) { t[p].u = id; return; }
int mid = (lv + rv) >> 1;
int v1 = getv(t[p].u, mid),
v2 = getv(id, mid);
if (v2 > v1) swap(t[p].u, id);
v1 = getv(t[p].u, lv);
v2 = getv(id, lv);
if (v2 > v1) upd(lt, lv, mid, id);
v1 = getv(t[p].u, rv);
v2 = getv(id, rv);
if (v2 > v1) upd(rt, mid + 1, rv, id);
return;
}
void add(int &p, int l, int r, int lv, int rv, int id) {
if (!p) p = ++now;
if (l <= lv && rv <= r) {
upd(p, lv, rv, id);
return;
}
int mid = (lv + rv) >> 1;
if (l <= mid) add(lt, l, r, lv, mid, id);
if (r > mid) add(rt, l, r, mid + 1, rv, id);
return;
}
int ask(int p, int lv, int rv, int x) {
int res = -inf;
if (!p) return -inf;
if (t[p].u) res = getv(t[p].u, x);
if (lv == rv) return res;
int mid = (lv + rv) >> 1;
if (x <= mid) res = max(res, ask(lt, lv, mid, x));
else res = max(res, ask(rt, mid + 1, rv, x));
return res;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(v[i].a), read(v[i].b), read(v[i].x);
b[++cnt] = v[i].a, b[++cnt] = v[i].b;
if (v[i].a > v[i].b) swap(v[i].a, v[i].b);
}
b[++cnt] = 1;
std::sort(b + 1, b + cnt + 1);
cnt = std::unique(b + 1, b + cnt + 1) - b - 1;
for (int i = 1; i <= n; ++i) {
v[i].a = std::lower_bound(b + 1, b + cnt + 1, v[i].a) - b;
v[i].b = std::lower_bound(b + 1, b + cnt + 1, v[i].b) - b;
a[1] -= 2 * v[i].x, a[v[i].a] += 2 * v[i].x, a[v[i].b] += 2 * v[i].x;
}
res = -inf;
for (int i = 1; i <= cnt; ++i) {
a[i] += a[i - 1];
seg[++tot].k = -4 * b[i];
seg[tot].b = a[i];
add(r, 1, lim, 1, lim, tot);
res = max(res, ask(1, 1, lim, b[i]) + a[i]);
}
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef int