算法基础课题解合集

离散化

离散化的特点是值域大，数量小，说白就是一种特殊的哈希，是一个离线算法。

离散化的实现

首先我们要先把原数组排序，然后再去重。

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

这样子，我们就成功离散化了。

对于这道题目而言，我们只要离散化后求前缀和即可。

离散化的查找

前面我们已经实现了离散化，但我们要如何查找一个元素呢。

显然，我们可以二分。

套二分板子即可。

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//这里设成300010是因为33行最多插入n个元素，40和41行最多插入m*2个元素，所以要设成300010
const int N = 300010;
typedef pair<int, int> PII;
int n, m;
int a[N], s[N];
//alls就是保存离散数据的数组
vector<int> alls;
//add是记录给x加上c操作的数组
//query是记录求a[l]~a[r]的和的数组
vector<PII> add, query;

//查找模板
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) 
    {
        int x, c;
        scanf("%d%d", &x, &c);
        alls.push_back(x);
        add.push_back({x, c});
    }
    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});
    }
    //离散化板子
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    for (auto item : add)
    {
        //x是离散后的下标
        int x = find(item.first);
        a[x] += item.second;
    }
    //求一遍前缀和
    for (int i = 1; i <= alls.size(); i ++)
        s[i] = s[i - 1] + a[i];
    //计算是s[l]~s[r]的和，那么就是前缀和模板s[r]-s[l - 1]
    for (auto item : query)
    {
        int l = find(item.first);
        int r = find(item.second);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

好啦，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$