题解:AT_agc063_f [AGC063F] Simultaneous Floor

· · 题解

把有序数对看成坐标,扔到平面直角坐标系上研究。下面记点 A(a_1,a_2),B(b_1,b_2)。不加说明时,我们均指第一象限。记值域为 V

发现点 P(x,y) 可以变成形如 (i,\lfloor\dfrac{y}{x}i\rfloor),(\lfloor\dfrac {x}{y}i\rfloor,i),i\in\mathbb Z 的点。不过还是有向下取整,不好描述。

那么倒过来看,对于 Q(p,q),能够到达它的 P 的集合是什么。

设直线 OP:y=kx,如果 P 能到达 Q,则 OP 必须穿过以 Q 为左下角、边长为 1 的正方形,穿过是指 OP 在正方形内的部分的长度 >0

Q_u(p,q+1),Q_r(p+1,q),则只要 OP\angle Q_rOQ_u 内部(不包括 OQ_u,OQ_r),其就会穿过这个正方形。

那么就有 k\in(k_{OQ_r},k_{OQ_u}),即能够到达 Q(p,q)P\in\{(x,y)|\dfrac{q}{p+1}<\dfrac y x<\dfrac{q+1}p\}

l_1=\dfrac{b_2}{b_1+1},r_1=\dfrac{b_2+1}{b_1},我们就可以算出经过 \le 1 次操作到达 B 的点的集合为 S_1=\{(x,y)|l_1<\dfrac y x<r_1\}

同理,设 l_2=\min\{\dfrac y{x+1}|(x,y)\in S_1\},r_2=\max\{\dfrac{y+1}x|(x,y)\in S_1\},则经过 \le 2 次操作到达 B 的点的集合为 S_2=\{(x,y)|l_2<\dfrac y x<r_2\}

更一般地,对于 t\ge 2,设 l_t=\min\{\dfrac y{x+1}|(x,y)\in S_{t-1}\},r_t=\max\{\dfrac{y+1}x|(x,y)\in S_{t-1}\},则经过 \le t 次操作到达 B 的点的集合为 S_t=\{(x,y)|l_t<\dfrac y x<r_t\}

先来研究已知 l_{t-1},r_{t-1} 如何求 l_t,r_t。下面只讨论 l_tr_t 是类似的。

问题相当于求最小的 \dfrac{y}{x+1},满足 l_{t-1}<\dfrac{y}{x}<r_{t-1}。考虑到 \dfrac{y}{x+1}=\dfrac{1}{\frac{x}{y}+\frac{1}{y}},即我们要 y 尽量小 \dfrac{x}{y} 尽量大。在 y 最小的同时取 x 最大即可,可以用反证法和一些缩放证明。

同理,求 r_t 时找满足 x 最小的最大 y 即可。

找到这样的 x,y 可以在 SBT 上二分实现。

接下来就是要求第一次满足 A\in S_tt。打表发现 l_t,r_t 在迭代若干轮之后就不变了,所以可以暴力求每一轮的 l_t,r_t 是多少。考虑到 l,r 在 SBT 上移动的过程,得到 x=1y=1 后就不会变了,所以迭代次数是 O(\log V) 的。

注意有点在坐标轴、y=x 上以及不在 y=x 同一侧的时候判无解。可以用关于 y=x 对称简化讨论。

总的复杂度是 O(T\log^2 V)