Perm Query

Time Limit : 2 sec, Memory Limit : 131072 KB

問題 G : Perm Query

問題文

\{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   mod10^9+7) を出力して終了する.そうでないなら 2 行目に戻る.

入力形式

入力は以下の形式で与えられる

N Q
p(1) p(2) ... p(N)
l_0 r_0
...
l_{Q-1} r_{Q-1}

出力形式

各クエリに対する出力を1行ずつ出力せよ.

制約

  • 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)… )))pk 回現れるもの.
  • 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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2013 , Day 2, Tokyo, Japan, 2013-09-21
http://acm-icpc.aitea.net/
http://jag2013summer-day2.contest.atcoder.jp/