G - Perm Query
Editorial
/
Time Limit: 2 sec / Memory Limit: 128 MB
\{1, 2, … , N\}の順列 (p(1), p(2), … , p(n)) が与えられる. (l_i, r_i) からなるクエリが Q 個与えられるので,各クエリに対して以下の擬似コードによる処理結果を出力せよ.
- ret := 0, (x(1), x(2), … , x(N)) := (1, 2, … , N) とおく.
- 各i ∈ \{1, 2, … , N\} について y(i) := p(x(i)) とする.
- 各i ∈ \{1, 2, … , N\} について x(i) = y(i)とする.
- ret := ret + x(l_i) + x(l_i+1) + … + x(r_i)
- もし (x(l_i), x(l_i+1), … , x(r_i)) = (l_i, l_i+1, … , r_i) なら (ret mod 10^9+7) を出力して終了する.そうでないなら 処理2に戻る.
入力形式
入力は以下の形式で与えられる
N Q p(1) p(2) ... p(N) l_1 r_1 ... l_Q r_Q
出力形式
各クエリに対する出力を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)… ))) で 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