AT_arc159_e [ARC159E] Difference Sum Query

给定一个正整数 $N$ 和 $M$ 组正整数对 $(a_0, b_0), \ldots, (a_{M-1}, b_{M-1})$（请注意 $a_i, b_i$ 的下标从 $0$ 开始）。 此外，存在如下定义的非负整数序列 $X=(x_1, \ldots, x_N)$。 - $x_i$ 的确定方式如下： 1. 令 $l=1, r=N, t=0$。 2. 令 $m=\left\lfloor \dfrac{a_{t \bmod M} \times l + b_{t \bmod M} \times r}{a_{t \bmod M} + b_{t \bmod M}} \right\rfloor$（$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。若 $m=i$，则令 $x_i=t$ 并结束步骤。 3. 若 $l \leq i < m$，则令 $r=m-1$，否则令 $l=m+1$。$t$ 的值加 $1$，回到步骤 2。 对于 $i=1,2,\ldots,Q$，请计算 $\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}|$ 的值。 在本题的约束下，可以证明答案不会超过 $10^{18}$。

输入以如下格式从标准输入给出。 > $N$ $M$ > $a_0$ $b_0$ > $\vdots$ > $a_{M-1}$ $b_{M-1}$ > $Q$ > $c_1$ $d_1$ > $\vdots$ > $c_Q$ $d_Q$

输出 $Q$ 行。第 $x$ 行输出对应 $i=x$ 的问题答案。

## 限制条件 - $2 \leq N \leq 10^{15}$ - $1 \leq M \leq 100$ - $1 \leq a_i, b_i \leq 1000$ - $\max \left( \dfrac{a_i}{b_i}, \dfrac{b_i}{a_i} \right) \leq 2$ - $1 \leq Q \leq 10^4$ - $1 \leq c_i < d_i \leq N$ - 所有输入均为整数 ## 样例解释 1 $X=(1,2,0,1,2)$。例如，$x_1$ 的确定过程如下： - 令 $l=1, r=5(=N), t=0$。 - 令 $m=3\left(=\left\lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right\rfloor\right)$。 - 因为 $l \leq 1 < m$，所以 $r=2(=m-1)$，$t$ 增加到 $1$。 - 令 $m=1\left(= \left\lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right\rfloor \right)$。$m=1$，所以 $x_1=1(=t)$，过程结束。 对于 $(c_i, d_i)$，例如 $(c_1, d_1)$，答案为 $\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| = |x_1-x_2| = 1$。 由 ChatGPT 4.1 翻译