← 返回题目列表

AtCoder · arc159_e

E. 差值和查询

中文机器翻译题面 查看原题

分数: 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 确定如下。
    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. 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