C++ 解法, 执行用时: 602ms, 内存消耗: 3120K, 提交时间: 2022-04-19 13:21:43

#include <bits/stdc++.h>

#define ll long long
#define N 100010

using namespace std;

int T, n, q, k;
ll sum, s[N], ans[N];

struct Q { int l, r, i; } qu[N];
unordered_map <int, int> cnt;

inline void add(int p) { sum += cnt[s[p]]++; }
inline void del(int p) { sum -= --cnt[s[p]]; }

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &n, &q, &k);
		for (int i = 1; i <= n; ++i) {
			scanf("%lld", s + i);
			(s[i] += s[i - 1]) %= k;
		}
		for (int i = 1; i <= q; ++i)
			scanf("%d %d", &qu[i].l, &qu[i].r), qu[i].i = i;
		int len = sqrt(n);
		sort(qu + 1, qu + q + 1, [len](const Q& a, const Q& b) {
			return (a.l / len ^ b.l / len) ? a.l < b.l : a.r < b.r;
		});
		cnt.clear(), sum = 0;
		int L = 1, R = 0;
		for (int i = 1; i <= q; ++i) {
			while (R < qu[i].r) add(++R);
			while (R > qu[i].r) del(R--);
			while (L > qu[i].l) add(--L);
			while (L < qu[i].l) del(L++);
			ans[qu[i].i] = sum + cnt[s[qu[i].l - 1]];
		}
		for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
	}

	return 0;
}