离散化 C++

题目

解题思路

• 将所有对坐标的访问用map映射到一个新的坐标轴上
• 再在新的坐标轴上进行加法
• 用前缀和快速求出区间的和

代码实现

#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;//N开大一点，不然会有越界错误
int a[N], s[N];

int main()
{
    int n, m;
    cin >> n >> m;
    
    vector<PII> add, query;//add存对坐标加法的行为， query存求区间和的请求
    vector<int> alls;//alls存所有对坐标的访问
    
    for (int i = 0; i < n; i ++ )
    {
        int x, plus;
        scanf("%d%d", &x, &plus);
        alls.push_back(x);
        add.push_back({x, plus});
    }
    
    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        alls.push_back(l); alls.push_back(r);
        query.push_back({l, r});
    }
    
    unordered_map<int, int> map;//map用来将alls中所有被访问的坐标映射到新的坐标上
    sort(alls.begin(), alls.end());//排序后才能达到有序映射的效果
    alls.erase(unique(alls.begin(), alls.end()), alls.end());//去重
    
    for (int i = 0; i < alls.size(); i ++ )
    {
        map[alls[i]] = i;//开始映射
    }
    
    for (int i = 0; i < add.size(); i ++ )
    {
    //在新坐标轴上做加法
        int idx = map[add[i].first], plus = add[i].second;
        a[idx] += plus;
    }
    
    //前缀和
    for (int i = 0; i < alls.size(); i ++ )
    {
        if (i == 0)
        {
            s[i] = a[i];
            continue;
        }
        s[i] = s[i - 1] + a[i];
    }
    
    for (int i = 0; i < query.size(); i ++ )
    {
        int l = map[query[i].first], r = map[query[i].second];
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

原文地址：https://blog.csdn.net/m0_62112384/article/details/144040401

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！