题解：AT_pakencamp_2024_day1_c One Half

题目分析

对每个查询区间 \([L_i,R_i]\)，先计算该区间的总和 \(S\)，再找到最小的 \(n\)（满足 \(L_i≤n≤R_i\)），使得从 \(L_i\) 到 \(n\) 的累加和首次超过 \(\frac{S}{2}\)。

由于数据范围为 \(N,Q≤2×10^5\)，暴力遍历每个查询的区间会导致 \(O(Q×N)\) 的时间复杂度（约 \(4×1010\) 次操作），必然超时。因此需要选择前缀和 + 二分查找的高效解法。

关键观察

数列中所有元素 \(A_i ≥1\)，因此前缀和数组是严格单调递增的。这意味着对于任意区间 \([L,R]\)，从 \(L\) 开始的累加和会随着 \(n\) 增大而严格增大，这满足二分查找的单调性条件，所以理所应当用二分。

Code

#include <iostream>
#include <vector>
using namespace std;int main() {int N;cin >> N;vector<long long> pre(N + 1, 0); // 前缀和数组for (int i = 1; i <= N; ++i) {long long a;cin >> a;pre[i] = pre[i-1] + a;}int Q;cin >> Q;while (Q--) {int L, R;cin >> L >> R;// 计算[L, R]的总和Slong long S = pre[R] - pre[L-1];long long st = S / 2;// 二分查找最小的n ∈ [L, R]int l = L, r = R;int ans = R; // 初始值设为R（最坏情况取到R）while (l <= r) {int mid = l + (r - l) / 2; // 避免溢出long long sum = pre[mid] - pre[L-1];if (sum > st) {ans = mid; // 找到可能的更小值，记录并向左收缩r = mid - 1;} else {l = mid + 1; // 不满足，向右找}}cout << ans << '\n';}return 0;
}