D题的莫队写法

比赛时没认真看范围，磨了半天磨了个莫队

#include <bits/stdc++.h>
#define fu(a, b, c) for (int a = b; a <= c; a++)
#define fd(a, b, c) for (int a = b; a >= c; a--)
#define mx(a, b) a = max(a, b)
#define mn(a, b) a = min(a, b)
using namespace std;
using ll = long long;
const int N = 1e5 + 1, B = sqrt(N);
int n, m, l, r, a[N];
ll cnt, ans[N];
unordered_map<int, int> mp;

int cal(int x) {
    int res = 1;
    for (int i = 2; i * i <= x; ++i) {
        int t = 0;
        while (x % i == 0)
            x /= i, ++t;
        res *= t + 1;
    }
    return x > 1 ? res << 1 : res;
}

struct q {
    int l, r, b, id;
    bool operator<(q a) {
        return b ^ a.b ? l < a.l : b & 1 ? r > a.r
                                         : r < a.r;
    }
} q[N];

inline void add(int x) { cnt += mp[a[x]], ++mp[a[x]]; }

inline void del(int x) { cnt -= mp[a[x]] - 1, --mp[a[x]]; }

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    fu(i, 1, n) cin >> a[i], a[i] = cal(a[i]);
    fu(i, 1, m) cin >> l >> r, q[i] = {l, r, l / B, i};
    sort(q + 1, q + m + 1);
    l = 1, r = 0;
    fu(i, 1, m) {
        // cout << q[i].l << ' ' << q[i].r << ' ';
        while (l > q[i].l)
            add(--l);
        while (r < q[i].r)
            add(++r);
        while (l < q[i].l)
            del(l++);
        while (r > q[i].r)
            del(r--);
        // for (auto [k, v] : mp)
        //     cout << k << ' ' << v << '\t';
        ans[q[i].id] = cnt;
        // cout << cnt << '\n';
    }
    fu(i, 1, m) cout << ans[i] << '\n';
}