Ґґлечики (Розбір)

Ідея

Для кожного запиту (l, r, k) потрібно порахувати \displaystyle\sum_{i=l}^{r} \frac{k}{a_i^{p_i}}, де p_i — найбільше ціле, для якого $k$ ділиться на a_i^{p_i} націло.

Наївний підхід (для кожного запиту пройти відрізок і для кожного глечика окремо обчислити степінь) працює за O(Q \cdot n \cdot \log k), що занадто повільно при n, Q \le 3 \cdot 10^6.

Ключове спостереження: переформулювання через дільники

Зафіксуємо $k$. Для кожного можливого значення a_i = d (де $d$ — дільник $k$) результат \frac{k}{d^p} однаковий і залежить лише від $k$ та $d$. Позначимо цей результат f(k, d).

Якщо ж a_i не ділить $k$, то p_i = 0 і внесок просто дорівнює $k$.

Тоді відповідь на запит можна записати так:

де \text{cnt}(d, l, r) — кількість елементів a_i = d на відрізку [l, r].

Передобчислення f(k, d)

Для кожного $k$ від $2$ до $mx$ та кожного його дільника $d$ обчислюємо f(k, d) = \frac{k}{d^p}, де $p$ — максимальний степінь $d$, що ділить $k$. Це можна зробити рекурсивно:

• Якщо \frac{k}{d} ділиться на $d$, то f(k, d) = f\!\left(\frac{k}{d},\; d\right).

• Інакше f(k, d) = \frac{k}{d}.

Дільники кожного числа $k$ знаходимо класичним "решетом": для кожного $i$ від $2$ до $mx$ додаємо $i$ в список дільників усіх його кратних. Сумарна кількість пар $(k,d)$ становить O(\mathit{mx} \ln \mathit{mx}).

Офлайн обробка запитів (sweep-line)

Щоб ефективно знаходити \text{cnt}(d, l, r) для кожного запиту, використовуємо прийом з префіксними сумами та офлайн sweep зліва направо по масиву $a$:

1. Для кожного запиту $i$ з відрізком [l_i, r_i] створюємо дві "події":

   • $+$ на позиції r_i (додати внесок);

   • $-$ на позиції l_i - 1 (відняти внесок).

2. Проходимо масив зліва направо, підтримуючи лічильник $\text{cnt}[v]$ — скільки разів значення $v$ зустрілося серед a_0, a_1, \ldots, a_i.

3. Коли натрапляємо на подію запиту $\text{num}$ на позиції $i$, перебираємо всі дільники $d$ числа k_{\text{num}} і додаємо (або віднімаємо) внесок f(k_{\text{num}}, d) \cdot \text{cnt}[d] до відповіді.

Таким чином, для кожного запиту ми отримуємо \text{cnt}(d, l, r) = \text{cnt}(d, 0, r) - \text{cnt}(d, 0, l-1) без явного обчислення.

Фінальна формула

Після sweep-line для кожного запиту $i$ маємо часткову суму \mathit{res}_i (внески від тих глечиків, чиє $a$-значення ділить k_i) та лічильник c_i (кількість таких глечиків). Доповнюємо відповідь внеском від "нейтральних" глечиків:

Асимптотика

• Побудова списків дільників (решето): O(\mathit{mx} \ln \mathit{mx}).

• Передобчислення $f$: O(\mathit{mx} \ln \mathit{mx}).

• Sweep-line: для кожного запиту перебираємо дільники k_i, яких у середньому O(\ln \mathit{mx}), тому сумарно O(Q \cdot d(k)), де $d(k)$ — кількість дільників $k$.

Загалом: O\!\left((n + \mathit{mx}) \ln \mathit{mx} + Q \cdot d(k)\right), де \mathit{mx} = \max(a_i, k_i) \le 5 \cdot 10^5.

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

using ll = long long;

const ll DIM = 500007;

struct query {
    int l, r, k;
};

vector < int > d[DIM];
vector < int > f[DIM];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;

    vector < int > a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    vector < query > Q(q);
    for(int i = 0; i < q; i++) {
        cin >> Q[i].l >> Q[i].r >> Q[i].k;
    }

    int mx = 0; 
    for(int i = 0; i < n; i++) mx = max(mx, a[i]);
    for(int i = 0; i < q; i++) mx = max(mx, Q[i].k);

    // sieve: build divisor lists
    for(int i = 2; i <= mx; i++) {
        for(int j = i; j <= mx; j += i) {
            d[j].push_back(i);
        }
    }
    vector < int > ptr(mx + 1, 0);

    // precompute f[k][j] = k / d[k][j]^p
    for(int i = 2; i <= mx; i++) {
        f[i].resize(d[i].size());
        for(int j = 0; j < (int)d[i].size(); j++) {
            if((i / d[i][j]) % d[i][j] == 0) {
                int to = i / d[i][j];
                while(d[to][ptr[to]] < d[i][j]) ptr[to]++;
                f[i][j] = f[to][ptr[to]];
            }
            else f[i][j] = i / d[i][j];
        }
    }

    // offline sweep
    vector < vector < int > > E(n);
    
    for(int i = 0; i < q; i++) {
        if(Q[i].l != 0) E[Q[i].l - 1].push_back(-(i + 1));
        E[Q[i].r].push_back((i + 1));
    }

    vector < ll > res(q);
    vector < ll > c(q);
    vector < int > cnt(mx + 1, 0);

    for(int i = 0; i < n; i++) {
        cnt[a[i]]++;

        for(auto e: E[i]) {
            int num = abs(e) - 1;
            for(int j = 0; j < (int)d[Q[num].k].size(); j++) {
                if(e > 0) {
                    c[num] += (ll)cnt[d[Q[num].k][j]];
                    res[num] += (ll)(f[Q[num].k][j])
                              * (ll)cnt[d[Q[num].k][j]];
                }
                if(e < 0) {
                    c[num] -= (ll)cnt[d[Q[num].k][j]];
                    res[num] -= (ll)(f[Q[num].k][j])
                              * (ll)cnt[d[Q[num].k][j]];
                }
            }
        }
    }

    for(int i = 0; i < q; i++) {
        res[i] += ll((Q[i].r - Q[i].l + 1) - c[i])
                * (ll)Q[i].k;
        cout << res[i] << endl;
    }

    return 0;
}