#P3762. 第1题-区间和
-
1000ms
Tried: 1
Accepted: 1
Difficulty: 4
-
算法标签>二分查找
第1题-区间和
解题思路
给定原数组 a 和重复次数数组 b,新数组 a' 是把 a_i 连续复制 b_i 次拼接而成。a' 的长度可能非常大(可达 ∑b_i),不能直接构造。
核心做法:前缀和 + 二分定位块。
-
预处理两条前缀数组
- 位置前缀(块边界):
prefB[i] = b_1 + b_2 + … + b_i。它表示在新数组a'中,第i个数所对应的“块”的右端位置。 据此,对任意位置p,用二分(lower_bound)找到最小的i使prefB[i] ≥ p,即可定位p属于的块下标i。 - 加权前缀和:
prefW[i] = a_1*b_1 + a_2*b_2 + … + a_i*b_i,用于快速求解整块区间的和。
- 位置前缀(块边界):
-
对每个查询区间
[l, r](在a'上的下标,1-based):-
用二分找到
s = lower_bound(prefB, l)与t = lower_bound(prefB, r),分别是l和r所在的块编号。 -
若
s == t:整个区间在同一块内,答案是(r - l + 1) * a[s]。 -
否则:
- 左端残块:从
l到块s的结尾,长度为prefB[s] - l + 1,贡献为(prefB[s] - l + 1) * a[s]; - 右端残块:从块
t的开始到r,长度为r - prefB[t-1],贡献为(r - prefB[t-1]) * a[t]; - 中间整块(若存在):
s+1 … t-1的总和为prefW[t-1] - prefW[s]。
- 左端残块:从
-
三部分之和即为答案。 整体不显式构造
a',每次查询仅做两次二分与 O(1) 计算。
-
算法要点:单调前缀 + 二分(lower_bound),块分解思想(两端残块 + 中间整块)。
复杂度分析
- 预处理:
prefB与prefW各 O(n) 时间与 O(n) 空间。 - 每次查询:两次二分 O(log n) + O(1) 计算。
- 总复杂度:O(n + q log n),空间复杂度 O(n),满足数据范围。
代码实现
Python
# 题面功能写在外部函数里:根据 a, b 与查询列表,返回每个查询的区间和
import sys
from bisect import bisect_left
def solve_queries(a, b, queries):
n = len(a) - 1 # a, b 使用 1-based
# 位置前缀(块右端位置)
prefB = [0] * (n + 1)
# 加权前缀和
prefW = [0] * (n + 1)
for i in range(1, n + 1):
prefB[i] = prefB[i - 1] + b[i]
prefW[i] = prefW[i - 1] + a[i] * b[i]
ans = []
for l, r in queries:
# 二分定位 l, r 所在块:第一个使 prefB[idx] >= p 的 idx
s = bisect_left(prefB, l, 1, n + 1)
t = bisect_left(prefB, r, 1, n + 1)
if s == t:
res = (r - l + 1) * a[s]
else:
# 左端残块
left_cnt = prefB[s] - l + 1
res = left_cnt * a[s]
# 右端残块
right_cnt = r - prefB[t - 1]
res += right_cnt * a[t]
# 中间整块
if t - s > 1:
res += prefW[t - 1] - prefW[s]
ans.append(res)
return ans
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
n = next(it)
a = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = next(it)
for i in range(1, n + 1):
b[i] = next(it)
q = next(it)
queries = []
for _ in range(q):
l = next(it); r = next(it)
queries.append((l, r))
res = solve_queries(a, b, queries)
out = '\n'.join(str(x) for x in res)
sys.stdout.write(out)
if __name__ == "__main__":
main()
Java
// 题面功能写在外部函数里:根据 a, b 与查询数组,返回每个查询的区间和
import java.io.*;
import java.util.*;
public class Main {
// 快速输入(根据数据量选择,防止超时)
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
long nextLong() throws IOException {
int c; long sgn = 1, x = 0;
do { c = read(); } while (c <= 32);
if (c == '-') { sgn = -1; c = read(); }
while (c > 32) {
x = x * 10 + (c - '0');
c = read();
}
return x * sgn;
}
int nextInt() throws IOException { return (int) nextLong(); }
}
// 二分:在 prefB[1..n] 中寻找第一个 >= p 的下标
static int lowerBound(long[] prefB, int n, long p) {
int lo = 1, hi = n, ans = n;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (prefB[mid] >= p) {
ans = mid;
hi = mid - 1;
} else lo = mid + 1;
}
return ans;
}
// 核心求解函数
static long[] solve(int n, long[] a, long[] b, int q, long[] L, long[] R) {
long[] prefB = new long[n + 1]; // 位置前缀(块右端)
long[] prefW = new long[n + 1]; // 加权前缀和
for (int i = 1; i <= n; i++) {
prefB[i] = prefB[i - 1] + b[i];
prefW[i] = prefW[i - 1] + a[i] * b[i];
}
long[] ans = new long[q];
for (int i = 0; i < q; i++) {
long l = L[i], r = R[i];
int s = lowerBound(prefB, n, l);
int t = lowerBound(prefB, n, r);
long res;
if (s == t) {
res = (r - l + 1) * a[s];
} else {
long leftCnt = prefB[s] - l + 1;
res = leftCnt * a[s];
long rightCnt = r - prefB[t - 1];
res += rightCnt * a[t];
if (t - s > 1) res += prefW[t - 1] - prefW[s];
}
ans[i] = res;
}
return ans;
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
long[] a = new long[n + 1];
long[] b = new long[n + 1];
for (int i = 1; i <= n; i++) a[i] = fs.nextLong();
for (int i = 1; i <= n; i++) b[i] = fs.nextLong();
int q = fs.nextInt();
long[] L = new long[q];
long[] R = new long[q];
for (int i = 0; i < q; i++) {
L[i] = fs.nextLong();
R[i] = fs.nextLong();
}
long[] ans = solve(n, a, b, q, L, R);
StringBuilder sb = new StringBuilder();
for (long v : ans) sb.append(v).append('\n');
System.out.print(sb.toString());
}
}
C++
// 题面功能写在外部函数里:根据 a, b 与查询,返回每个查询的区间和
#include <bits/stdc++.h>
using namespace std;
// 求解函数:返回每个查询答案
vector<long long> solve(int n, const vector<long long>& a, const vector<long long>& b,
const vector<pair<long long,long long>>& queries) {
vector<long long> prefB(n + 1, 0); // 位置前缀(块右端)
vector<long long> prefW(n + 1, 0); // 加权前缀和
for (int i = 1; i <= n; ++i) {
prefB[i] = prefB[i - 1] + b[i];
prefW[i] = prefW[i - 1] + a[i] * b[i];
}
vector<long long> ans;
ans.reserve(queries.size());
for (auto [l, r] : queries) {
// 在 prefB[1..n] 上 lower_bound
int s = int(lower_bound(prefB.begin() + 1, prefB.begin() + n + 1, l) - prefB.begin());
int t = int(lower_bound(prefB.begin() + 1, prefB.begin() + n + 1, r) - prefB.begin());
long long res = 0;
if (s == t) {
res = (r - l + 1) * a[s];
} else {
// 左端残块
long long leftCnt = prefB[s] - l + 1;
res += leftCnt * a[s];
// 右端残块
long long rightCnt = r - prefB[t - 1];
res += rightCnt * a[t];
// 中间整块
if (t - s > 1) res += prefW[t - 1] - prefW[s];
}
ans.push_back(res);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<long long> a(n + 1), b(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
int q; cin >> q;
vector<pair<long long,long long>> queries(q);
for (int i = 0; i < q; ++i) {
long long l, r; cin >> l >> r;
queries[i] = {l, r};
}
vector<long long> res = solve(n, a, b, queries);
for (auto v : res) cout << v << "\n";
return 0;
}
题目内容
你有两个长度为 n 的数组 a 和 b ,数组 a 中每个元素 ai 复制 bi 次后,可以得到新数组 a′ 。例如,假设 a=[8,9,7,5,7],b=[1,2,2,1,3] ,则新数组 a′=[8,9,9,7,7,5,7,7,7] 。
你需要回答 q 次询问,其中第 i 次询问会给出两个参数 li 和 ri,你需要计算新数组 a′ 中下标在 [li,ri] 范围内所有元素的和。
输入描述
输入第一行有一个整数 n(1≤n≤105),表示数组的长度。
第二行有 n 个整数 a1,a2,…,an(1≤ai≤n) ,表示题目给定的数组 a 。
第三行有 n 个整数 b1,b2,…,bn(1≤bi≤n) ,表示题目给定的数组 b 。
第四行有一个整数 q(1≤q≤105) ,表示询问的次数。
接下来 q 行中第 i 行有两个正整数 li 和 ri(1≤li,ri≤∑i=1nbi) ,表示第 i 次询问中的下标范围。
输出描述
对于每一个询问,输出一行一个整数,表示新数组 a′ 下标范围内所有元素的和。
样例1
输入
5
8 9 7 5 7
1 2 2 1 3
2
3 7
1 9
输出
35
66
说明
新数组 a′=[8,9,9,7,7,5,7,7,7] ,对于第一个询问,答案为 9+7+7+5+7=35 ;对于第二个询问,实际上问的是新数组的和,答案为 8+9+35+7+7=66 。