一次合并代表有一条编号 $[l,m]$ 中的点到编号 $(m,r]$ 中的点的边，即一条跨过 $m$ 这条缝的边。现在考虑 $S$ 中的合并对应一条边对应 $T$ 中的合并，从而我们要找到一个 $S$ 和 $T$ 中的合并的匹配。我们从低到顶考虑 $S$ 的合并；对于 $S$ 中最小的 $1+1$ 的合并，它只能跨过唯一一个缝，因此它对应的 $T$ 中的合并的是唯一的（由这个缝的位置决定）；在进一步合并时，我们可以归纳证明匹配的唯一性。现在我们有若干 $[l_1,m] (m,r_1]$ 和 $[l_2,m] (m,r_2]$ 的匹配，每个匹配对应 $(m-\max(l_1,l_2)+1) (\min(r_1,r_2)-m)$ 条边。相乘即可。

E. E-Circuit Is Now on Sale!

题意

给定一个网格，一个格子可能是数、四联通的导线 #、运算符、输出、空。电路构成一棵树，每个运算符都有两个输入和一个输出。求输出。保证中间结果 $\leq 10^{18}$ 。 $n,m\leq 50$ 。

题解

一个比较简单的实现是从输出 DFS。

F. The Farthest Point

题意

给定一个长方体的三边长度。求离一个顶点最远的点（沿长方体表面算）的距离。

题解

考虑展开长方体。先枚举答案所在的底面，接下来任意取一个不在这个面上的点，根据展开方式不同，这个点可以对应到 $6$ 个坐标（有的坐标会能与长方形内部所有点求距离，有的则会被一条线段隔开）。拿出它们两两的垂直平分线、拿出底面的四条边、拿出顶点到隔开线段的端点，得到 $21$ 条直线；两两求交点，得到大量候选点，每个候选点求它到 $6$ 个坐标的距离最小值，对所有候选点取最大值即可。

G. Beyond the Former Explorer

题意

交互题。有一个 $(2n+1)\times (2n+1)$ 的网格，你初始位于正中。有一个未知的藏宝点。某些格子有箭头，箭头串成了一条从起点到藏宝点的路径。你一步可以向上下左右移动一个，交互库返回到达的格子上的箭头方向。你要在 $30000$ 步内到达藏宝点。 $n\leq 2000$ 。

题解

二分。维持藏宝点可能的区域为一个矩形，每次轮流横着、竖着将其分为两半，查询分界线左右的两排格子，由此可以得到两个小矩形的边界处有多少向内的箭头、向外的箭头，从而确定藏宝点在哪个小矩形内。

I. Greatest of the Greatest Common Divisors

题意

给定一序列。多次查询一个区间内任取两个不同的数的最大的最大公约数。 $n\leq 10^5$ 。 $n,q,a_i\leq 10^5$ 。

题解

枚举约数，每个约数对应若干个位置，从而对应若干个 $l\leq p_i,r\geq p_{i+1}$ 的可能的区间。查询对应二维数点。