分数: 900 点
问题陈述
给你一个正整数 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 确定如下。
- 让 l=1, r=N,和 t=0.
- 让 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 并终止。
- If l \leq i \lt m,让 r=m-1;否则,让 l=m+1。增量 t by 1 并返回步骤 2。
查找 \sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| 为 i=1,2,\ldots,Q.
可以证明答案最多是 10^{18} 在这个问题的约束下。
约束
- 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 \lt d_i \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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.
样本输入 1
5 1 1 1 3 1 2 2 4 3 5
示例输出 1
1 3 2
我们有 X=(1,2,0,1,2)。例如, x_1 确定如下。
- 让 l=1, r=5(=N),和 t=0.
- 让 m=3(=\left \lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right \rfloor).
- 自从 l \leq 1 \lt m,让 r=2(=m-1)。增量 t by 1 to 1.
- 让 m=1(= \left \lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right \rfloor )。自从 m=1,让 x_1=1(=t) 并终止。
问题的答案 例如, (c_1,d_1)是 \sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| = |x_1-x_2| = 1.
示例输入 2
1000000000000000 2 15 9 9 15 3 100 10000 5000 385723875 150 17095708
示例输出 2
19792 771437738 34191100