Problem:


問題 G : Perm Query 

問題文

\{1,&thinsp; 2,&thinsp; …&thinsp;,&thinsp; N\}の順列 (p(1),&thinsp; p(2),&thinsp; …&thinsp;,&thinsp; p(n)) が与えられる．
(l_i,&thinsp; r_i) からなるクエリが Q 個与えられるので，各クエリに対して以下の擬似コードによる処理結果を出力せよ．

ret &thinsp; := &thinsp; 0, (x(1),&thinsp; x(2),&thinsp; …&thinsp;,&thinsp; x(N)) &thinsp;:=&thinsp; (1,&thinsp; 2,&thinsp; …&thinsp;,&thinsp; N) とおく．

各i &thinsp; &in; \{1, &thinsp; 2, &thinsp;…&thinsp;, &thinsp; N\} について y(i) := p(x(i)) とする．

各i &thinsp; &in; \{1, &thinsp; 2, &thinsp;…&thinsp;, &thinsp; N\} について x(i) &thinsp; = &thinsp;y(i)とする．

ret &thinsp; := &thinsp;ret + x(l_i) + x(l_i+1) + …&thinsp; + x(r_i)

もし (x(l_i),&thinsp; x(l_i+1),&thinsp; …&thinsp;,&thinsp; x(r_i)) = (l_i,&thinsp; l_i+1,&thinsp; …&thinsp;,&thinsp; r_i) なら (ret &ensp; 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,&thinsp; p_2,&thinsp; …&thinsp;,&thinsp; p_N) は (1,&thinsp; 2,&thinsp; …&thinsp;,&thinsp; N) の順列になっている．

各 i に対して，ある 1 ≤ k ≤ 40 が存在して，p^k(i)=i となる．ここで，p^k(i) は p(p(p(…&thinsp;p(i)…&thinsp;))) で p が k 回現れるもの．

1 ≤ l_i &thinsp; ≤ &thinsp; r_i &thinsp; ≤ N

入出力例

入力例 1

5 2
5 1 2 3 4
1 1
2 4

出力例 1

15
45

擬似コード中の順列(x(1), &thinsp; x(2), &thinsp; …&thinsp;, &thinsp;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



Sample input:
5 2
5 1 2 3 4
1 1
2 4


Sample output:
15
45

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m

def solve():
    MOD = 10**9 + 7

    N, Q = map(int, readline().split())
    *P, = map(int, readline().split())
    S = [0]*N
    K = [0]*N
    used = [0]*N
    for i in range(N):
        if used[i]:
            continue
        vs = [i]
        s = i+1
        used[i] = 1
        v = P[i]-1
        while v != i:
            vs.append(v)
            s += v+1
            used[v] = 1
            v = P[v]-1
        l = len(vs)
        for v in vs:
            S[v] = s
            K[v] = l % MOD
    N0 = 2**(N-1).bit_length()
    S0 = [0]*(2*N0)
    K0 = [1]*(2*N0)
    for i in range(N):
        S0[N0-1+i] = S[i]
        K0[N0-1+i] = K[i]
    def calc(k0, k1, s0, s1):
        g = gcd(k0, k1)
        return k0 // g * k1, ((s0*k1 + s1*k0) // g) % MOD

    for i in range(N0-2, -1, -1):
        K0[i], S0[i] = calc(K0[2*i+1], K0[2*i+2], S0[2*i+1], S0[2*i+2])

    def query(l, r):
        L = l + N0; R = r + N0
        k = 1
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                k, s = calc(k, K0[R-1], s, S0[R-1])

            if L & 1:
                k, s = calc(k, K0[L-1], s, S0[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    for i in range(Q):
        l, r = map(int, readline().split())
        write("%d\n" % query(l-1, r))
solve()