include <stdio.h> int main(){ int n,x,y,q,k,a[100009],i,b[100009],c; scanf("%d",&n);c=n; while(n--) {scanf("%d%d",&x,&y); a[x]=y;}i=1; while(i<=c){b[i]=a[i]+b[i-1]; i++;} scanf("%d",&q); while(q--){ scanf("%d",&k); printf("%d\n",b[k]); }}

解题思路

1. 用数组 a 统计每一天实际存入的总金额（若同一天多次存钱，需累加 y）。
2. 预处理前缀和数组 b：b[i] 表示前 i 天的总存款（递推式：b[i] = b[i-1] + a[i]）。
3. 对于每次询问 k，直接输出 b[k]（前缀和数组可直接得到前 k 天的总和）。

通过前缀和预处理，将多次查询的总时间复杂度优化至 (O(n + q))。

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n;
    cin >> n;
    int a[n + 5] = {0};
    int b[n + 5] = {0};
    for (int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        a[x] += y;
    }
    for (int i = 1; i <= n; i++){
        b[i] = b[i - 1] + a[i];
    }
    int q;
    cin >> q;
    while (q--){
        int k;
        cin >> k;
        cout << b[k] << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}