解题思路

给定原数组 a 和重复次数数组 b，新数组 a' 是把 a_i 连续复制 b_i 次拼接而成。a' 的长度可能非常大（可达 ∑b_i），不能直接构造。 核心做法：前缀和 + 二分定位块。

1. 预处理两条前缀数组

   • 位置前缀（块边界）：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，用于快速求解整块区间的和。

2. 对每个查询区间 [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$ 中每个元素 $a_i$ 复制 $b_i$ 次后,可以得到新数组 $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$ 次询问会给出两个参数 $l_i$ 和 $r_i$，你需要计算新数组 $a'$ 中下标在 $[l_i,r_i]$ 范围内所有元素的和。

输入描述

输入第一行有一个整数 $n(1≤n≤10^5)$，表示数组的长度。

第二行有 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤n)$ ，表示题目给定的数组 $a$ 。

第三行有 $n$ 个整数 $b_1,b_2,…,b_n(1≤b_i≤n)$ ，表示题目给定的数组 $b$ 。

第四行有一个整数 $q(1≤q≤10^5)$ ，表示询问的次数。

接下来 $q$ 行中第 $i$ 行有两个正整数 $l_i$ 和 $r_i(1≤l_i,r_i≤\sum^n_{i=1}b_i)$ ，表示第 $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$ 。