Codeforces Round #182 (Div. 1) D. Yaroslav and Divisors

#include <bits/stdc++.h>

const int N = 2e5 + 7;

struct Que {
    int l, r, id;
    bool operator < (const Que &p) const {
        return r < p.r;
    }
} que[N];
int n, m, p[N], pos[N];
std::vector<int> vec[N];
int ans[N];

struct Bit {
    int tree[N];
    inline int lowbit(int x) { return x & -x; }
    inline void add(int x) {
        for (int i = x; i <= n; i += lowbit(i))
            tree[i]++;
    }
    inline int query(int x) {
        int ans = 0;
        for (int i = x; i; i -= lowbit(i))
            ans += tree[i];
        return ans;
    }
    inline int query(int l, int r) {
        return query(r) - query(l - 1);
    }
} bit;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", p + i), pos[p[i]] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = p[i]; j <= n; j += p[i]) {
            int l = i, r = pos[j];
            if (l > r) std::swap(l, r);
            vec[r].push_back(l);
        }
    }
    for (int i = 1; i <= m; i++) 
        scanf("%d%d", &que[i].l, &que[i].r), que[i].id = i;
    std::sort(que + 1, que + 1 + m);
    int cur = 1;
    for (int i = 1; i <= m; i++) {
        while (cur <= que[i].r) {
            for (int j = 0; j < vec[cur].size(); j++)
                bit.add(vec[cur][j]);
            cur++;
        }
        ans[que[i].id] = bit.query(que[i].l, que[i].r);
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}