题解 | #盒饭盲盒#

#include<bits/stdc++.h>

using i64 = long long;

const int N = 3e5 + 1;

i64 pre[N];
int L[N], R[N], bel[N], a[N], e[N];

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

	int n, q; std::cin >> n >> q;
	for (int i = 1; i <= n; i += 1) {
		std::cin >> a[i];
	}

	const int B = sqrt(n);
	const int T = (n + B - 1) / B;

	auto cg = [&](int id) {
		for (int i = L[id]; i <= R[id]; i += 1) {
			e[i] = a[i];
		}
		std::sort(e + L[id], e + R[id] + 1);
		for (int i = L[id]; i <= R[id]; i += 1) {
			pre[i] = e[i];
			if (i >= L[id] + 1) {
				pre[i] += pre[i - 1];
			}
		}
	};

	for (int i = 1; i <= T; i += 1) {
		L[i] = (i - 1) * B + 1, R[i] = std::min(n, i * B);
		for (int j = L[i]; j <= R[i]; j += 1) {
			bel[j] = i;
		}
		cg(i);
	}

	while (q--) {
		int l, r, k; std::cin >> l >> r >> k;
		i64 ans = 0;
		if (bel[l] == bel[r]) {
			for (int i = l; i <= r; i += 1) {
				ans += std::min(a[i] % k, k - (a[i] % k));
			}
		} else {
			for (int i = l; i <= R[bel[l]]; i += 1) {
				ans += std::min(a[i] % k, k - (a[i] % k));
			}
			for (int i = L[bel[r]]; i <= r; i += 1) {
				ans += std::min(a[i] % k, k - (a[i] % k));
			}
			for (int j = bel[l] + 1; j <= bel[r] - 1; j += 1) {
				auto it = std::upper_bound(e + L[j], e + R[j] + 1, k / 2) - e;
				ans += pre[it - 1];
				ans += (R[j] - it + 1) * k - pre[R[j]] + pre[it - 1];
			}
		}
		std::cout << ans << "\n";
	}

	return 0;
}