CF Round 881 (Div. 3)
Div. 3 果然简单，虽然但是，我还是有 1 道题没有想出来。
A.Sasha and Array Coloring
排序双指针向内即可。
https://codeforces.com/contest/1843/submission/210855587
B.Long Long
好啊，就是这道题没想出来。
Virtual Contest 上完成了一半。
考虑把符号相同（0 与任何数符号相同）的合并。
因为放在一起操作显然最优。
bool sgn_eq(int x, int y) {
return (x * y) >= 0;
}
然后你就得到了一个 ... + - + - ... 正负交替的序列。
那么，很明显，正数与负数的个数相差不超过一，也就是说花费 1 的代价将负数转化为正数的行为是不可取的（我就死在这上面，如此弱智的东西……），于是记录所有负数的个数即可。
有可能溢出，要精细实现
https://codeforces.com/contest/1843/submission/211085413
也可以直接合并负数序列（忽略 0 的情况）
https://codeforces.com/contest/1843/submission/211082437
C.Sum in Binary Tree
会手写堆的人都会写……
Submission #210856724 - Codeforces
D.Apple Tree
弱智题……记录一下每一个节点有多少个叶子节点。输出相乘的结果即可。
https://codeforces.com/contest/1843/submission/210857337
E.Tracking Segments
其实可以改一下题目，变为：
对于每一条线段，求出其变成
beautiful segment的时间，如果不会变，则输出-1，顺便强制在线一波。这样代码难度递增。
我首先想到的是一个在线做法。
只要在这个区间内修改了严格大于一半的点，那么一个区间就变得 美丽。
那么什么最早是什么时候？
定义序列 \(t_i\) 表示第 \(i\) 个点变成 \(1\) 的时间，如果没有修改则 \(t_i = \inf\)。
对于区间 \([l, r]\)，设 \(k = \lfloor \frac {l - r + 1} 2 \rfloor + 1\)，则对于序列 \(t\) 的区间 \([l, r]\) 第 \(k\) 小即为所求。
如果为 \(\inf\) 则不会变得 美丽。
但是显然这太过于复杂。
考虑离线处理每一个线段，并且二分答案。
明显答案具有单调性，如果在 \(t\) 时变得 美丽，则之后一直会很 美丽。
我说的不是我们
我们只加入前 \(mid\) 个点，然后用一个前缀和一一判断有没有 美丽 的线段即可。
如果是 美丽 的，则满足在这个区间内有 \(\ge k\) 个点变成了 \(1\)。
https://codeforces.com/contest/1843/submission/211083551
F.Omsk Metro
自己做的时候胡的性质：
对于一个路径 \(p\)，定义其最大子段和为 \(mx_p\)，最小子段和为 \(mn_p\)。
那么可以拼凑出来的区间为 \([mx_p, mn_p]\)。
感性证明一下：
这里不妨把一条路径拍扁成一条链，设为 \([l, r]\)。
我们考虑加入一个点 \(r\) 对于一条路径 \([l, r]\) 的影响。
设 \(suf_x\) 为以 \(x\) 为右端点，可以凑出来的权值的集合。
考虑递推，有 \(suf_x = \{0, w(x)\} \cup （suf_{x - 1} + w(x))\)。
于是对于区间 \([l, r]\) 有 \(S = \bigcup_{l \le x \le r} suf_x\)。
其实不难发现，\(suf_x\) 的上下界每一次最多只会变化 \(1\)，也就是说，如果可以凑出 \(x (x \ge 0)\)，那么一定可以凑出 \([0, x]\)。负数的情况同理。
所以我们考虑求出最大的，和最小的子段和即可 \(O(1)\) 判断……
实现上也就是树链剖分加上基本的求区间最大子段和的思路即可。