Nobody is needed (Codeforces 1946F)
Tags: DP, 2-sat

Oleg received a permutation $$$a$$$ of length $$$n$$$ as a birthday present.Oleg's friend Nechipor asks Oleg $$$q$$$ questions, each question is characterized by two numbers $$$l$$$ and $$$r$$$, in response to the question Oleg must say the number of sets of indices $$$(t_1, t_2, \ldots, t_k)$$$ of any length $$$k \ge 1$$$ such that:   $$$l \le t_i \le r$$$ for each $$$i$$$ from $$$1$$$ to $$$k$$$.  $$$t_i < t_{i+1}$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$.  $$$a_{t_{i+1}}$$$ is divisible by $$$a_{t_i}$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$. Help Oleg and answer all of Nechipor's questions.

Input: Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of sets of input data. The description of the sets of input data follows.The first line of each set of input data contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — the length of the permutation and the number of Nechipor's questions.The second line of each set of input data contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation $$$a$$$ itself.In each of the next $$$q$$$ lines of each set of input data, there are two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the next question of Nechipor.It is guaranteed that the sum of the values of $$$n$$$ and the sum of the values of $$$q$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each set of input data, output the answers to all of Nechipor's questions.

Note: All suitable arrays in the first set of input data: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 3$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 6, 7$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 5$$$), ($$$2, 6$$$), ($$$2, 7$$$), ($$$2, 8$$$), ($$$2, 6, 7$$$), ($$$6, 7$$$).All suitable arrays in the fourth set of input data: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 2$$$), ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 5$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 8$$$), ($$$1, 2, 4$$$), ($$$1, 2, 6$$$), ($$$1, 2, 8$$$), ($$$1, 2, 4, 8$$$), ($$$1, 3, 6$$$), ($$$1, 4, 8$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$2, 8$$$), ($$$2, 4, 8$$$), ($$$3, 6$$$), ($$$4, 8$$$).

Sample Inputs:
4
8 8
2 1 6 3 5 4 8 7
1 8
2 8
1 7
1 6
1 3
5 8
4 4
2 3
1 1
1
1 1
3 3
3 2 1
1 2
1 3
2 3
8 1
1 2 3 4 5 6 7 8
1 8

Sample Outputs:
20 15 18 12 5 5 1 3
1
2 3 2
27

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v, w):
    return u << 40 ^ v << 20 ^ w
t = int(input())
ans = []
for _ in range(t):
    (n, q) = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    p = [0] * (n + 1)
    for i in range(1, n + 1):
        p[a[i]] = i
    q0 = [0] * q
    for i in range(q):
        (l, r) = map(int, input().split())
        q0[i] = f(l, r, i)
    q0.sort()
    tree = [0] * (n + 5)
    dp = [0] * (n + 1)
    ans0 = ['1'] * q
    for l in range(n, 0, -1):
        i = a[l]
        dp[i] = 1
        for j in range(i, n + 1, i):
            if dp[j]:
                (k, x) = (p[j], dp[j])
                while k < len(tree):
                    tree[k] += x
                    k += k & -k
            if l <= p[j]:
                for k in range(2 * j, n + 1, j):
                    if p[j] <= p[k]:
                        dp[k] += dp[j]
            dp[j] = 0
        while q and q0[q - 1] >> 40 == l:
            q -= 1
            (r, i) = (q0[q] >> 20 & 1048575, q0[q] & 1048575)
            ans1 = 0
            while r > 0:
                ans1 += tree[r]
                r -= r & -r
            ans0[i] = str(ans1)
        if not q:
            break
    ans.append(' '.join(ans0))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())
t = inp()
for i in range(t):
    (n, q) = inlt()
    a = [0] + inlt()
    p = [0] * (n + 1)
    for i in range(1, n + 1):
        p[a[i]] = i
    q0 = [0] * q
    for i in range(q):
        (l, r) = inlt()
        q0[i] = l << 40 ^ r << 20 ^ i
    q0.sort()
    fenwick = [0] * (n + 1)
    dp = [0] * (n + 1)
    ans0 = [1] * q
    for l in range(n, 0, -1):
        i = a[l]
        dp[i] = 1
        for j in range(i, n + 1, i):
            if l <= p[j]:
                for k in range(2 * j, n + 1, j):
                    if p[j] < p[k]:
                        dp[k] += dp[j]
            if dp[j]:
                (k, x) = (p[j], dp[j])
                while k <= n:
                    fenwick[k] += x
                    k += k & -k
            dp[j] = 0
        while q0 and q0[-1] >> 40 == l:
            (r, i) = (q0[-1] >> 20 & 1048575, q0.pop() & 1048575)
            ans1 = 0
            while r > 0:
                ans1 += fenwick[r]
                r -= r & -r
            ans0[i] = ans1
        if not q0:
            break
    print(' '.join(map(str, ans0)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v, w):
    return u << 40 ^ v << 20 ^ w
t = int(input())
ans = []
for _ in range(t):
    (n, q) = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    p = [0] * (n + 1)
    for i in range(1, n + 1):
        p[a[i]] = i
    q0 = [0] * q
    for i in range(q):
        (l, r) = map(int, input().split())
        q0[i] = f(l, r, i)
    q0.sort()
    tree = [0] * (n + 5)
    dp = [0] * (n + 1)
    ans0 = ['1'] * q
    for l in range(n, 0, -1):
        i = a[l]
        dp[i] = 1
        for j in range(i, n + 1, i):
            if dp[j]:
                (k, x) = (p[j], dp[j])
                while k < len(tree):
                    tree[k] += x
                    k += k & -k
            if l <= p[j]:
                for k in range(2 * j, n + 1, j):
                    if p[j] <= p[k]:
                        dp[k] += dp[j]
            dp[j] = 0
        while q0 and q0[-1] >> 40 == l:
            (r, i) = (q0[-1] >> 20 & 1048575, q0.pop() & 1048575)
            ans1 = 0
            while r > 0:
                ans1 += tree[r]
                r -= r & -r
            ans0[i] = str(ans1)
        if not q0:
            break
    ans.append(' '.join(ans0))
sys.stdout.write('\n'.join(ans))