← 返回题目列表

AtCoder · icpc2013summer_day2_g

G. 烫发查询

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

\{1,  2,  … ,  N\}的排列 给出了 (p(1),  p(2),  … ,  p(n)) 。 由 (l_i,  r_i) 组成的查询 给出了 Q ,因此对每个查询使用以下伪代码输出处理结果。

  1. ret   :=   0, (x(1),  x(2),  … ,  x(N))  :=  (1,  2,  … ,  N) 。 关于
  2. 各i   ∈ \{1,   2,  … ,   N\} 关于 y(i) := p(x(i)) 。
  3. 各i   ∈ \{1,   2,  … ,   N\} 关于 x(i)   =  y(i)。
  4. ret   :=  ret + x(l_i) + x(l_i+1) + …  + x(r_i)
  5. 如果 (x(l_i),  x(l_i+1),  … ,  x(r_i)) = (l_i,  l_i+1,  … ,  r_i) 如果 (ret 模组 输出 10^9+7) 并退出。如果不是,则返回流程2。

入力形式

输入按以下格式给出

N Q
p(1) p(2) ... p(N)
l_1 r_1
...
l_Q r_Q

出力形式

一次一行打印每个查询的输出。 它是

制約

  • 1 ≤ N ≤ 10^5
  • 1 ≤ Q ≤ 10^4
  • (p(1),  p(2),  … ,  p(N)) 是 (1,  2,  … ,  N) 的排列。 对于
  • 各 i ,有 1 ≤ k ≤ 40 存在,p^k(i)=i 变为。在这里, 在p^k(i) 是 p(p(p(… p(i)… ))) 出现 p 是 它可能以 k 次的东西。
  • 1 ≤ l_i   ≤   r_i   ≤ N

入出力例

入力例 1

5 2
5 1 2 3 4
1 1
2 4

出力例 1

15
45

伪代码中的排列(x(1),   x(2),   … ,  x(N))更改如下。

1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
1 2 3 4 5

入力例 2

10 5
3 1 2 5 4 10 6 7 9 8
1 10
1 5
3 3
5 10
9 10

出力例 2

660
90
6
178
67