2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest

菜得不行。

Problem A

Solved by ultmaster. 01:22 (+2)

题意：$a$, $b$, $c$ 是递增数列，求 $(i,j,k)$ 对数满足 $|a_i-b_j| \le d, |a_i-c_k| \le d, |b_j-c_k| \le d$。

题解：枚举 $a$ 中的元素，$b$ 中满足的显然是一个区间，对于这个区间内的数，满足的 $c$ 的右端点可以通过预处理得到。通过预处理前缀和应该不难解决。不过大概是做烦了，鉴于大家都过得飞快。

先写错了一个变量 WA 了一发，然后不知道什么地方崩了 long long（还立了个 flag 说绝对不会是这个问题的），被 zerol 全部改成 long long 过了。

Solved by ultmaster. 03:19 (+)

题意：在树上找一个点集，使得每条路径都与这个点集有交集。

题解：如果树是一条链，显然是一个经典的「丽娃河装路灯」问题（之前还讨论过它的树状数组优化）。那么放到树上，我们就按照 LCA 的深度排序，路灯肯定装在 LCA 上。同样使用树状数组优化，加个树链剖分就可以。

Solved by zerol. 02:56 (+3)