AT_arc159_e.[ARC159E] Difference Sum Query

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一个正整数 $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$ $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

1000000000000000 2
15 9
9 15
3
100 10000
5000 385723875
150 17095708

输出#2

19792
771437738
34191100

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?