记录编号	615917	评测结果	AAAAAAAAAAAA
题目名称	[ICPC2026河南省赛]来点离线做法	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	5.199 s
提交时间	2026-05-26 18:56:11	内存使用	126.22 MiB

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<int> a(n);
    int max_a = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        max_a = max(max_a, a[i]);
    }
    int V = max_a;

    int B = max(1, (int)sqrt(n));
    int M = (n + B - 1) / B;

    vector<vector<int>> pre(M + 1, vector<int>(V + 1, 0));
    vector<vector<long long>> f(M + 1, vector<long long>(B + 1, 0));

    for (int i = 1; i <= M; ++i) {
        memcpy(pre[i].data(), pre[i - 1].data(), (V + 1) * sizeof(int));
        memcpy(f[i].data(), f[i - 1].data(), (B + 1) * sizeof(long long));

        int L = (i - 1) * B;
        int R = min(i * B, n);
        for (int pos = L; pos < R; ++pos) {
            int x = a[pos];
            pre[i][x]++;
            for (int k = 1; k <= B; ++k) {
                f[i][k] += x / k;
            }
        }
    }

    for (int i = 0; i <= M; ++i) {
        for (int x = 1; x <= V; ++x) {
            pre[i][x] += pre[i][x - 1];
        }
    }

    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        --l; --r;
        int lb = l / B, rb = r / B;
        long long ans = 0;

        if (lb == rb) {
            for (int i = l; i <= r; ++i) ans += a[i] / k;
        } else {
            int end_left = (lb + 1) * B;
            for (int i = l; i < end_left; ++i) ans += a[i] / k;
            int start_right = rb * B;
            for (int i = start_right; i <= r; ++i) ans += a[i] / k;

            if (lb + 1 <= rb - 1) {
                if (k <= B) {
                    ans += f[rb][k] - f[lb + 1][k];
                } else {
                    int max_v = V / k;
                    for (int v = 0; v <= max_v; ++v) {
                        int low = v * k;
                        int high = min((v + 1) * k - 1, V);
                        int cnt = pre[rb][high] - (low > 0 ? pre[rb][low - 1] : 0)
                                - (pre[lb + 1][high] - (low > 0 ? pre[lb + 1][low - 1] : 0));
                        ans += 1LL * v * cnt;
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}