考点：前缀和

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 1e5，q ≤ 1e5
• 元素值域：a_i ≤ 1e9，l ≤ 1e9，r ≤ 1e9（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：前缀和

本题切入点

先统计未知元素个数 cnt 与已知元素之和 base，则 min = base + cnt×l，max = base + cnt×r，每次询问 O(1)。

预处理前缀和数组，把「区间求和」从 O(n) 降到 O(1)。

思路框架（前缀和 通法 · 非本题专属）

1. 预处理 pre[i] = a[1]+...+a[i]。
2. 区间 [l, r] 的和 = pre[r] - pre[l-1]。
3. 若题目是「多次区间修改 + 最后统一查询」，改用差分数组：d[l]+=v, d[r+1]-=v，最后做一遍前缀和还原。
4. 二维情况用二维前缀和（容斥原理）。

实现要点：开 long long，避免 n 较大时求和溢出。

复杂度：时间 预处理 O(n)，每次查询 O(1) ｜ 空间 O(n)

该范式的通法易错点

• pre 数组下标没留出 0 号位导致 l-1 越界。
• 求和结果超出 int 范围（1e5 个 1e9 相加会溢出 32 位整数）。

对照本题

• 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 2 / 1 0 3 / 1 2 / 4 4 → 输出 5 6 / 8 8

只有第二个元素是未知的。

第一次询问，数组最小的和是 1+1+3=5，最大的和是 1+2+3=6。

第二次询问，显然数组的元素和必然为 8。