Qablar (Həll təhlili)

İdeya

Hər sorğu üçün (l, r, k), \displaystyle\sum_{i=l}^{r} \frac{k}{a_i^{p_i}} ifadəsini hesablamaq lazımdır, burada p_i — $k$ ədədinin a_i^{p_i}-yə bölündüyü ən böyük tam ədəddir.

Sadə yanaşma (hər sorğu üçün seqmenti gəzib, hər qab üçün dərəcəni ayrıca hesablamaq) O(Q \cdot n \cdot \log k) vaxtında işləyir, bu isə n, Q \le 3 \cdot 10^6 üçün çox yavaşdır.

Əsas müşahidə: bölənlər vasitəsilə yenidən ifadə

$k$-nı sabit götürək. a_i = d mümkün qiymətləri üçün (burada $d$ — $k$-nın bölənidir), \frac{k}{d^p} qiyməti eynidir və yalnız $k$ və $d$-dən asılıdır. Bu qiyməti f(k, d) ilə işarə edək.

Əgər a_i ədədi $k$-nı bölmürsə, onda p_i = 0 olur və töhfə sadəcə $k$-ya bərabərdir.

Onda sorğunun cavabı belə yazıla bilər:

burada \text{cnt}(d, l, r) — [l, r] seqmentində a_i = d olan elementlərin sayıdır.

f(k, d)-nin əvvəlcədən hesablanması

$2$-dən $mx$-ə qədər hər $k$ üçün və onun hər bir böləni $d$ üçün f(k, d) = \frac{k}{d^p} hesablayırıq, burada $p$ — $d$-nin $k$-ni bölən maksimum qüvvətidir. Bunu rekursiv şəkildə etmək olar:

• Əgər \frac{k}{d} ədədi $d$-yə bölünürsə, onda f(k, d) = f\!\left(\frac{k}{d},\; d\right).

• Əks halda, f(k, d) = \frac{k}{d}.

Hər ədədin bölənlərini klassik "sieve" ilə tapırıq: $2$-dən $mx$-ə qədər hər $i$ üçün, onun bütün qatlarının bölən siyahısına $i$ əlavə edirik. $(k,d)$ cütlərinin ümumi sayı O(\mathit{mx} \ln \mathit{mx})-dir.

Sorğuların oflayn emalı (sweep-line)

Hər sorğu üçün \text{cnt}(d, l, r)-ni səmərəli tapmaq üçün prefix cəmlərdən və $a$ massivində soldan sağa oflayn sweep-dən istifadə edirik:

1. [l_i, r_i] seqmentli hər $i$ sorğusu üçün iki "hadisə" yaradın:

   • r_i mövqeyində $+$ (töhfəni əlavə et);

   • l_i - 1 mövqeyində $-$ (töhfəni çıx).

2. Massivi soldan sağa gəzərək, $\text{cnt}[v]$ sayğacını saxlayın — a_0, a_1, \ldots, a_i arasında $v$ qiymətinin neçə dəfə göründüyünü.

3. $i$ mövqeyində $\text{num}$ sorğu hadisəsinə rast gəldikdə, k_{\text{num}}-ın bütün bölənləri $d$ üzrə iterasiya edin və cavaba f(k_{\text{num}}, d) \cdot \text{cnt}[d] töhfəsini əlavə edin (və ya çıxın).

Beləliklə, hər sorğu üçün \text{cnt}(d, l, r) = \text{cnt}(d, 0, r) - \text{cnt}(d, 0, l-1)-i açıq hesablama olmadan əldə edirik.

Yekun formula

Sweep-line-dən sonra, hər $i$ sorğusu üçün bizdə qismən cəm \mathit{res}_i ($a$-qiyməti k_i-ni bölən qabların töhfələri) və sayğac c_i (belə qabların sayı) olur. Cavabı "neytral" qabların töhfəsi ilə tamamlayırıq:

Mürəkkəblik

• Bölən siyahılarının qurulması (sieve): O(\mathit{mx} \ln \mathit{mx}).

• $f$-nin əvvəlcədən hesablanması: O(\mathit{mx} \ln \mathit{mx}).

• Sweep-line: hər sorğu üçün k_i-nin bölənləri üzrə iterasiya edirik, onların sayı orta hesabla O(\ln \mathit{mx})-dir, deməli ümumilikdə O(Q \cdot d(k)), burada $d(k)$ — $k$-nın bölənlərinin sayıdır.

Ümumi: O\!\left((n + \mathit{mx}) \ln \mathit{mx} + Q \cdot d(k)\right), burada \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;
}