题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N] = { 0 }, s[N] = { 0 };  // 初始化数组以避免垃圾值

vector<int> alls;  // 存储所有的点
vector<PII> add;   // 存储添加的值
vector<PII> query; // 存储查询的区间

// 二分查找，找到第一个不小于x的下标
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + (r - l) / 2; // 修正 mid 的计算
        if (alls[mid] < x) l = mid + 1;
        else r = mid; // 这里是找到不小于x的位置
    }
    return r + 1; // 返回下标（1-based index）
}

vector<int>::iterator unique(vector<int>& a)
{
    int j = 0;
    for (int i = 0; i < a.size(); i++)
        if (!i || a[i] != a[i - 1])
            a[j++] = a[i];
    // a[0] ~ a[j-1] 所有不重复的数

    return a.begin() + j;
}

int main()
{
    cin >> n >> m;

    // 读入添加的信息
    for (int i = 0; i < n; i++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({ x, c });
        alls.push_back(x);
    }

    // 读入查询的区间
    for (int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({ l, r });
        alls.push_back(l);
        alls.push_back(r);
    }

    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls), alls.end());

    // 处理添加的信息
    for (auto i : add)
    {
        int x = find(i.first);
        a[x] += i.second; // 累加对应下标的值
    }

    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i++)
    {
        s[i] = s[i - 1] + a[i]; // 计算前缀和
    }

    // 处理查询
    for (auto i : query)
    {
        int l = find(i.first), r = find(i.second);
        cout << s[r] - s[l - 1] << endl; // 修正查询的计算
    }

    return 0;
}

时间复杂度

参考文献

C++ 代码

blablabla