Ta chia các truy vấn thành hai loại: truy vấn với bước “lớn” ($d>\sqrt{n}$) và với bước nhỏ ($d\leq\sqrt{n}$). Khi truy vấn có bước lớn, ta có thể cập nhật trâu mảng $A$, do số phần tử ta cập nhật không vượt quá $O(n/d)=O(\sqrt{n})$.

Với các truy vấn bước nhỏ, ta xét bài toán thế sau: Cho mảng $A$ gồm $n$ phần tử, ban đầu các phần tử đều là $0$, cùng với $q$ truy vấn $(l,r)$: tăng $A_l$ lên $1$, $A_{l+1}$ lên $2$,…, $A_r$ lên $r-l+1$. Cho biết mảng $A$ sau $q$ truy vấn (nói cách khác, bài toán với $d=1$).

Để làm bài toán này, ta thấy rằng trong một truy vấn, $A_i$ tăng một lượng bằng $i-(l-1)$. Trong đó, phần $-(l-1)$ tương ứng với tăng đoạn lên một hằng số, và có kỹ thuật mảng cộng dồn khá phổ biến để xử lý điều này. Còn với phần tăng $i$, do mỗi $A_i$ chỉ có thể tăng $i$ nên ta chỉ cần lưu lại $A_i$ đã được cộng vào một lượng $i$ bao nhiêu lần, chẳng hạn trong một mảng $cnt$, trên đó ta cũng có thể thực hiện kỹ thuật mảng cộng dồn nói trên (tăng đoạn $[l,r]$ của mảng $cnt$ lên $1$). Nếu chưa hiểu, bạn có thể tham khảo đoạn code để giải bài toán này ở dưới:

int l, r;
for (int _ = 0; _ < q; ++_){
    cin >> l >> r;
    co[l] -= (l - 1);
    if (r < n) co[r + 1] += (l - 1);
    cnt[l] += 1;
    if (r < n) cnt[r + 1] -= 1;
}
for (int i = 1; i <= n; ++i){
    co[i] += co[i - 1];
    cnt[i] += cnt[i - 1];
    A[i] = co[i] + i * cnt[i];
}

Ý tưởng giải với $d=1$ có thể tổng quát hóa thành giải với mọi $d\leq\sqrt{n}$. Để làm điều này, ta chỉ cần tạo $\sqrt{n}$ mảng $co$ và $cnt$ để giải riêng với từng $d$ để cộng lại vào mảng $A$ cuối cùng. Tuy nhiên, phải để ý cộng/trừ đúng giá trị.

Độ phức tạp thời gian của thuật toán là $O(\sqrt{n}\times(n+q))$. Code mẫu (sử dụng mảng chỉ số $0$ để tiện chia block độ dài $d$):

#include <bits/stdc++.h>
#define ll long long
#define debug(x) cout << #x << " = " << x << '\n'
#define all(a) a.begin(), a.end()
using namespace std;
const int mxn = 1e5 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 7e18;
int n, q, S;
ll a[mxn], pref[2][320][mxn];
void solve(){
    cin >> n >> q;
    S = sqrt(n);
    for (int _ = 0, l, r, d; _ < q; ++_){
        cin >> l >> r >> d;
        r -= ((r - l) % d);
        --l, --r;
        if (d > S){
            for (int i = l; i <= r; i += d){
                a[i] += 1ll * ((i - l) / d + 1);
            }
        } else {
            // cập nhật co
            int u = (l / d) + 1;
            pref[0][d][l] -= (u - 1);
            if (r + d < n) pref[0][d][r + d] += (u - 1);
            // cập nhật cnt
            pref[1][d][l] += 1;
            if (r + d < n) pref[1][d][r + d] -= 1;
        }
    }
    for (int d = 1; d <= S; ++d){
        for (int i = 0; i < n; ++i){
            if (i - d >= 0){
                pref[0][d][i] += pref[0][d][i - d];
                pref[1][d][i] += pref[1][d][i - d];
            }
            ll val = (i / d) + 1;
            a[i] += pref[0][d][i] + val * pref[1][d][i];
        }
    }
    for (int i = 0; i < n; ++i)
        cout << a[i] << ' ';
    cout << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}