本题是经典的莫队(Mo's Algorithm)，因为区间左右移动对答案的影响可以在\(O(1)\)时间内算出。
莫队的核心思想是对各个询问作合理的排序，然后进行\(O(n\sqrt n)\)数量级次移动(左区间+1,-1或右区间+1,-1称为一次移动)，每次移动的代价是\(O(1)\)，所以总的时间复杂度是\(O(n\sqrt n)\)

Code:

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

const int siz = 2000, maxval = 5e5+5;
struct query{
    int l, r, index;
    bool operator< (const query& q)
    {
        if(l/siz != q.l/siz) return l/siz < q.l/siz;
        return r/siz < q.r/siz;
    }
};
int nowl = 1, nowr = 0; //初始没有元素，初始区间[1,0]
long long nowans = 0;
long long num[maxval];

void ins(int x){num[x]++; nowans+=num[x]-1;}
void del(int x){num[x]--; nowans-=num[x];} 

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k, q;
    cin>>n>>k>>q;
    
    long long a[n+1], pre[n+1] = {0};
    for(int i=1;i<=n;i++) cin>>a[i];
    partial_sum(a+1, a+n+1, pre+1);
    for(auto& i: pre) i%=k; 
    query Q[q];
    long long ans[q];
    for(int i=0;i<q;i++) cin>>Q[i].l>>Q[i].r, Q[i].index = i;
    sort(Q,Q+q);
    
    for(auto [l, r, index] : Q) // C++17及以上支持结构化绑定
    {
        while(nowr < r) ins(pre[++nowr]);
        while(nowl > l) ins(pre[--nowl]);
        while(nowr > r) del(pre[nowr--]);
        while(nowl < l) del(pre[nowl++]);
        ans[index] = nowans + num[pre[l-1]];
    }
    for(auto i: ans) cout<<i<<'\n';
    return 0;
}