一、题意理解

我们有一个长度为 $n$ 的序列 $a$，每个 $a_i \in [0,p-1]$。

定义：对于任意子区间 $[i,j]$，它的“恐惧总值”是 $\left( \sum_{k=i}^j a_k \right) \bmod p$ 注意这里是 模 $p$ 后的值，不是区间和本身。

给定 $q$ 个询问 $[l,r]$，要求： $ \min_{l \le i \le j \le r} \left[ \left( \sum_{k=i}^j a_k \right) \bmod p \right] $ 即 $[l,r]$ 内所有子区间模 $p$ 的最小值。

---

二、初步分析

设 $S[i]$ 表示前缀和： $S[i] = \sum_{k=1}^i a_k$ 那么区间 $[i,j]$ 的和为 $S[j] - S[i-1]$。

我们要求的是： $ \min_{l \le i \le j \le r} \left[ (S[j] - S[i-1]) \bmod p \right] $ 注意模 $p$ 运算，所以结果在 $[0,p-1]$ 之间。

---

三、关键观察

设 $x = S[j] - S[i-1]$。

• 如果 $x < p$，那么 $x \bmod p = x$。
• 如果 $x \ge p$，那么 $x \bmod p = x - p$。

因为 $a_i \ge 0$，所以 $x \ge 0$。

因此： $ (S[j] - S[i-1]) \bmod p = \begin{cases} S[j] - S[i-1], & \text{if } S[j] - S[i-1] < p \\ S[j] - S[i-1] - p, & \text{if } S[j] - S[i-1] \ge p \end{cases} $

---

1. 最小值可能的情况

情况 1：存在 $i,j$ 使得 $S[j] = S[i-1]$，那么差为 $0$，模 $p$ 也是 $0$，这是可能的最小值。

情况 2：如果不存在差 $0$，那么最小值可能是某个很小的正数 $t$，即 $S[j] - S[i-1] = t$ 且 $t < p$。

情况 3：也可能最小值来自 $S[j] - S[i-1] \ge p$ 的情况，此时模 $p$ 的值是 $S[j] - S[i-1] - p$，这个值可能是负数吗？不会，因为模运算结果在 $[0,p-1]$，所以这里 $S[j] - S[i-1] - p \ge 0$ 吗？不一定，如果 $S[j] - S[i-1] \ge p$，那么 $S[j] - S[i-1] - p \ge 0$ 是对的。所以模 $p$ 的结果总是非负的。

---

实际上，$(S[j] - S[i-1]) \bmod p$ 就是取 $S[j] - S[i-1]$ 除以 $p$ 的余数，所以结果在 $0$ 到 $p-1$ 之间。

---

四、问题转化

我们要找： $ \min_{l \le i \le j \le r} ( (S[j] - S[i-1]) \bmod p ) $ 等价于： $ \min_{l-1 \le i < j \le r} ( (S[j] - S[i]) \bmod p ) $ 其中 $i$ 从 $l-1$ 到 $r-1$，$j$ 从 $i+1$ 到 $r$。

---

设 $T[i] = S[i] \bmod p$，那么 $T[i] \in [0,p-1]$。

那么： $(S[j] - S[i]) \bmod p = (T[j] - T[i]) \bmod p$ 这里 $(x \bmod p)$ 表示取 $x$ 模 $p$ 的最小非负剩余。

注意：$(T[j] - T[i]) \bmod p$ 等于：

• 如果 $T[j] \ge T[i]$，则为 $T[j] - T[i]$
• 如果 $T[j] < T[i]$，则为 $T[j] - T[i] + p$

所以我们要最小化： $\min \big( T[j] - T[i],\ T[j] - T[i] + p \big)$ 其中 $T[j] - T[i]$ 只在 $T[j] \ge T[i]$ 时有效，否则用第二个。

---

五、进一步简化

我们要求： $ \min_{l-1 \le i < j \le r} \min\big( T[j] - T[i],\ T[j] - T[i] + p \big) $ 其中 $T[j] - T[i]$ 在 $T[j] \ge T[i]$ 时取，否则取 $T[j] - T[i] + p$。

---

观察：如果我们把 $T$ 数组在区间 $[l-1, r]$ 排序，那么相邻两项的差（模 $p$ 意义下）的最小值很可能就是答案。

定理：最小值要么是 $0$（存在 $T[i] = T[j]$），要么是某个相邻差值（在排序后的环状意义下）。

理由：
在模 $p$ 下，$T$ 值可以看作环上 $0..p-1$ 的点。我们要找两个点 $T[i], T[j]$ 使得环上距离最小。这个最小距离一定出现在排序后相邻的项之间（环上相邻），或者等于 $0$（重复点）。

所以算法：

1. 检查区间内是否有两个前缀和模 $p$ 相等 → 答案是 $0$。
2. 否则，把区间内的 $T$ 值排序，计算相邻差（包括首尾环状差 $T_{\text{first}} + p - T_{\text{last}}$），取最小差作为答案。

---

六、考虑数据范围与实现

$n$ 最大 $6\times 10^6$，$q$ 没说但应该很大。

我们不能对每个询问排序（$O(\text{len} \log \text{len})$ 会超时）。

但题目有条件：

• 3/4 概率区间长度 $\le len$
• 1/4 概率区间长度 $> len$
• 并且 $len$ 在子任务中给出（如 2650, 8500）

所以我们可以：

• 对小区间直接暴力排序找最小差
• 对大连间，由于数据随机，很可能存在两个 $T$ 值相等（生日悖论），直接返回 $0$；如果不存在，则最小值很可能很小，可以枚举较小的差值来检查。

---

七、高效算法思路

对于小区间（长度 $\le len$）：

• 把区间内的 $T$ 值取出，排序，计算相邻差以及环状差，取最小值。
• 复杂度 $O(len \log len)$。

对于大连间（长度 $> len$）：

• 由于 $a_i$ 随机，$T[i]$ 可以看作在 $[0,p-1]$ 随机。
• 区间长度很大时，根据生日悖论，几乎必然存在两个 $T$ 值相等，直接返回 $0$。
• 为了保险，可以检查是否存在 $T$ 值重复（用哈希表），如果没有再采用其他方法（但概率极低）。

---

八、最终算法框架

1. 读入 $n,p,a$，计算前缀和 $S$ 和 $T[i] = S[i] \bmod p$。
2. 对每个询问 $[l,r]$：
   • 如果 $r-l+1 > len$，直接输出 $0$（大概率正确，因为随机数据下几乎一定有重复 $T$ 值）。
   • 否则：
     • 收集 $T[l-1 .. r]$ 到数组 $B$
     • 排序 $B$
     • $ans = p$
     • 遍历 $i$ 从 $1$ 到 $|B|-1$：$ans = \min(ans, B[i] - B[i-1])$
     • $ans = \min(ans, B[0] + p - B[|B|-1])$
     • 输出 $ans$

---

九、代码实现（C++）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
using namespace std;
#define LL long long
#define LD long double
const int inf = 1e9 + 17;
const int NN = 6e6 + 17;
const int MM = 1e3 + 17;
const int MAXSIZE = 1 << 22;
inline char gc() {
    static char In[MAXSIZE], *at = In, *en = In;

    if (at == en) {
        en = (at = In) + fread(In, 1, MAXSIZE, stdin);
    }

    return at == en ? EOF : *at++;
}
inline int read() {
    char c;

    while (c = gc(), !(c >= '0' && c <= '9') && c != '-') {}

    bool f = c == '-';
    long long x = f ? 0 : c - '0';

    for (c = gc(); c >= '0' && c <= '9'; c = gc()) {
        x = x * 10 + c - '0';
    }

    return f ? -x : x;
}
void open() {
    freopen("sb.in", "r", stdin);
    //  freopen("test.out","w",stdout);
}
void close() {
    fclose(stdin);
    fclose(stdout);
}
int n, m;
int glob = 0;
int t[NN] = {};
int a[NN] = {};
int mod;
set<int> s;
int main() {
    //open();
    int n = read();
    int mod = read();

    for (int i = 1; i <= n; ++i)
        a[i] = (a[i - 1] + read()) % mod;

    int qu = read();

    for (int ti = 1; ti <= qu; ++ti) {
        int l = read(), r = read();
        int ans = mod - 1;
        int len = r - l + 1;

        if (len >= 2e4) {
            printf("0\n");
            continue;
        }

        if ((LD)mod / (len * len / 2) >= 8 * log(len)) {
            s.clear();
            s.insert(a[l - 1]);

            for (int i = l; i <= r; ++i) {
                set<int>:: iterator it = s.upper_bound(a[i]);

                if (it == s.begin())
                    it = s.end();

                it--;
                ans = min(ans, (mod + a[i] - *it) % mod);
                s.insert(a[i]);
            }

            printf("%d\n", ans);
            continue;
        }

        for (int res = 0; res < mod; ++res) {
            ++glob;
            bool fl = 0;

            for (int j = l - 1; j <= r; ++j) {
                if (t[(a[j] + mod - res) % mod] == glob) {
                    printf("%d\n", res);
                    fl = 1;
                    break;
                }

                t[a[j]] = glob;
            }

            if (fl)
                break;
        }

    }

    close();
    return 0;
}

---

十、总结

本题的关键在于：

1. 将问题转化为在模 $p$ 意义下找前缀和数组 $T$ 在区间内的最小环上距离。
2. 利用数据随机性质，对大连间直接返回 $0$。
3. 对小区间暴力排序找最小差。

这样可以在大数据范围内高效地回答询问。