前文。

和序列与查询 $4$ 差不多。

不难发现这个题做前缀和后和 $4$ 本质相同，沿用前面的方法即可。

#include<bits/stdc++.h>
#define F(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
int n, m, k, q, a[100005], f[520][100005], b[1000005];
int kc, ks, L[2005], R[2005], B[100005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    m = k;
    ++n;
    F(i, 2, n) cin >> a[i];
    F(i, 1, n) a[i] = (a[i - 1] + a[i]) % k;
//    F(i, 1, n)
//        cout << a[i] << " ";
//    cout << "\n";
    kc = 258, ks = (n + kc - 1) / kc;
    F(i, 1, ks){
        L[i] = R[i - 1] + 1, R[i] = i == ks ? n : L[i] + kc - 1;
        F(j, L[i], R[i]) B[j] = i;
        F(j, L[i], n){
            if (!b[a[j]]) b[a[j]] = j;
            f[i][j] = max(f[i][j - 1], j - b[a[j]]);
        }
        F(j, 0, m) b[j] = 0;
        b[a[L[i]]]++;
        for (int j = L[i] - 1; j; j--){
            if (!b[a[j]]) b[a[j]] = j;
            f[i][j] = max(f[i][j + 1], b[a[j]] - j);
        }
        F(j, 0, m) b[j] = 0;
    }
    cin >> q;
    while (q--){
        int l, r, ans = 0;
        cin >> l >> r;
        ++r;
        if (B[l] == B[r]){
            F(i, l, r){
                if (!b[a[i]]) b[a[i]] = i;
                ans = max(ans, i - b[a[i]]);
            }
            F(i, l, r) b[a[i]] = 0;
        }else{
            ans = max(f[B[l] + 1][r], f[B[r]][l]);
            F(i, l, R[B[l]]) if (!b[a[i]]) b[a[i]] = i;
            F(i, L[B[r]], r) if (b[a[i]]) ans = max(ans, i - b[a[i]]);
            F(i, l, R[B[l]]) b[a[i]] = 0;
        }
        cout << ans << "\n";
    }
    return 0;
}