試験 / Examination
三维偏序板子，CDQ 即可。
ビーバーの会合 / Meetings
首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。
我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。
那么直接递归处理链上每个点剩下的子树即可。询问次数大概是 $\mathcal{O}(18n)$ 的。
ナン / Naan
我们可以对每个人求出他的好感度的 $n$ 等分点的位置。
那么从左往右考虑每一段，每次找一个没选的这一段等分点最靠左的人，把从这个点切开后得到的左边那一段给他。
这样子每个人拿到的段的右端点都是他的一个等分点，但左端点一定小于等于上一个等分点，所以一定满足条件。
ふたつのアンテナ / Two Antennas
先考虑 $i<j,h_i>h_j$ 的情况，另一种情况将 $h_i$ 取相反数后等价。
考虑扫描线。对于某个 $i$，它可以和 $[i+a_i,i+b_i]$ 内的通信站通信，于是我们可以把它在 $i+a_i$ 处加入，$i+b_i+1$ 处删除。对于某个 $j$，可以和它通信的通信站在 $[j-b_j,j-a_j]$ 内。
我们维护一个 $d_i$ 表示每个 $i$ 对应的最大成本。那么对于某个 $j$，我们相当于把 $[j-b_j,j-a_j]$ 内的 $d_i$ 对 $h_i-h_j$ 取 $\max$。这样子询问就是询问一段区间的 $d_i$ 的最大值。
我们还需要考虑通信站怎么加入删除。我们再维护一个 $c_i$，当 $i$ 被加入时设成 $h_i$，否则设成 $-\infty$，并把上面改成对 $c_i-h_j$ 取 $\max$ 即可。
这样子我们只需要支持单点修改 $c_i$、区间 $d_i$ 对 $c_i-h_j$ 取 $\max$、区间 $d_i$ 求 $\max$，线段树维护即可。
ふたつの料理 / Two Dishes
设 $y_i=\max\left\{j|\sum_{k=1}^i a_k+\sum_{k=1}^j b_k\leq s_i\right\}$，$x_i=\max\left\{j|\sum_{k=1}^j a_k+\sum_{k=1}^i b_k\leq t_i\right\}$。
那么整个过程相当于在从 $(0,0)$ 走到 $(n,m)$，如果 $(i,y_i)$ 在路径上方或路径上则可以得到 $p_i$ 的分数，如果 $(x_i,i)$ 在路径下方或路径上则可以得到 $q_i$ 的分数。
这两种分数不好处理，我们先把所有 $p_i$ 加上，然后改成如果 $(i-1,y_i+1)$ 在路径下方或路径上则可以得到 $-p_i$ 的分数。
那么有一个显然的 DP：设 $dp_{i,j}$ 表示从 $(0,0)$ 走到 $(i,j)$ 的最大分数，转移为
$$
dp_{i,j}=\max\left\{dp_{i-1,j}+s_{i,j},dp_{i,j-1}\right\}
$$
其中 $s_{i,j}$ 为 $(i,j)$ 下方的点权和。
可以发现这个 DP 本质就是先对一些后缀加一个值，然后求一遍前缀 $\max$。考虑差分，那么我们先对若干个单点修改，然后再把负数变成 $0$ 并把它后面第一个非 $0$ 数加上这个负数即可。可以用 set 维护非 $0$ 位置、线段树维护差分。
ふたつの交通機関 / Two Transportations
咕咕咕。
指定都市 / Designated Cities
我们相当于要让被免费掉的最大。
$E=1$ 时，直接换根 DP 即可；$E=2$ 时，我们一定会选某个节点子树内最深的两个叶子，同样可以 DP。
然后有一个结论：设 $S_i$ 为 $E=i$ 时最优方案选择的城市，则当 $i\geq 2$ 时 $S_i\subseteq S_{i+1}$。证明不会。
因此我们只要每次找一个新增贡献最大的点加入即可，可以用 DFS 序+线段树维护。
ランプ / Lamps
可以发现，不会有两个切换操作相交，不会有两个赋值操作相交，且一定可以让赋值操作在切换操作之前完成。
于是可以考虑 DP。设 $dp_{i,0/1/2}$ 表示前 $i$ 个位置，当前位置赋值为 $0$ / 赋值为 $1$ / 没有被赋值时操作区间端点的最小个数，转移很简单。
为了方便算答案我们在最后各加一个 $0$，答案即为 $dp_{n,2}/2$。
時をかけるビ太郎 / Bitaro, who Leaps through Time
这里只考虑 $a<c$ 的情况，$a=c$ 的情况很简单，$a>c$ 的情况翻转后做一遍即可。
我们把时间轴画出来，那么移动大概是这样的：
我们把第 $i$ 个城市的时间都减去 $i$，变成这样子：
这样子移动就是横竖的了。
然而我们要支持修改和查询。对于相邻的两个城市，假设它们的区间分别是 $[a,b]$ 和 $[c,d]$，那么这两个城市合在一起是不是就相当于 $[a,b]\cap[c,d]$ 呢？
其实并不是，因为有可能两个区间的交为空集。这时我们可以用一个三元组 $(a,b,w)$ 来表示一段路径，意思是进来的时刻至多是 $a$、出去的时刻至少是 $b$、消耗的代价是 $w$。举个例子：如果 $r_i<l_{i+1}$，三元组为 $(r_i,l_{i+1},0)$；如果 $l_i>r_{i+1}$，三元组为 $(l_i,r_{i+1},l_i-r_{i+1})$。
同时可以发现，二元组、三元组之间很好合并，能走就走、不能走就调即可。还可以发现，这个合并是满足结合律的。于是用线段树维护即可。
ケーキの貼り合わせ / Cake 3
可以发现，$\sum_{j=1}^m\lvert c_{k_j}-c_{k_{j+1}}\rvert$ 的下界是 $2(c_{\max}-c_{\min})$，而且只要按照 $c$ 排序即可达到这个下界。
把所有蛋糕按 $c$ 从小到大排序，那么相当于要枚举一个区间 $[l,r]$，然后选 $m$ 个最大的 $v$ 出来，再减去 $2(c_r-c_l)$ 后更新答案。
可以发现对于每个 $l$，最优的 $r$ 是单调不降的，也就是有决策单调性，分治求出每个 $l$ 对应的最优的 $r$ 即可。求解时需要求一段区间的前 $m$ 大值，可以用主席树维护。
合併 / Mergers
一棵树满足条件当且仅当对于每条边，其两端都存在同色的点。
于是我们可以先对于每种颜色，把它在树上的最小连通块缩成一个点。
这样子树上就没有同色的点了。而我们每次可以把一条路径的两个端点改成同色的从而让这条路径满足条件，因此答案即为最小路径覆盖，即叶子数除以 $2$ 再上取整。
鉱物 / Minerals
首先我们先用 $2n$ 次询问把所有矿物划分成两个集合 $A,B$，使得相同的矿物在不同集合内。
考虑分治，每次加入 $A$ 中的前若干个元素，然后即可确定 $B$ 中和它相同的矿物的编号，即可往下分治处理。
假设我们取前 $p\times len$ 个元素，则复杂度是 $\mathcal{T}(n)=\mathcal{T}(pn)+\mathcal{T}((1-p)n)+\mathcal{O}((1+p)n)$，不知道为啥当 $p=\frac{3-\sqrt{5}}{2}$ 时最优。
实现时需要注意不能把当前层的操作撤回，而应维护一下每层前若干个矿物是是否已经被加入。
1 条评论
orz