[基础算法](7)离散化

引言

对于值域比较大、个数比较少的的序列,有些题我们需要用这些数作为下标,而我们不能开一个那么大的数组,这个时候我们就需要其映射到从0开始的自然数,只存储用到的数即可

离散化的要点:将用到的数保持下来,映射到数组内,然后二分去查找

  • 去除重复元素
  • 二分查找离散化后的值

区间和

模板题:802. 区间和 - AcWing题库

image-20210711020119330

代码:

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

using namespace std;

const int N=300010;//坐标x的数量上限为1e5,两个坐标l,r的数量上限也为1e5,所以加起来为3*le5;
typedef pair<int,int> PII;//pair<int,int>类似于结构体的简写版,typedef定义了一个新的类型PII(跟结构体定义了一个结构体类型然后使用相似)

int a[N],s[N];

vector<int> alls;
vector<PII> add,query;
//使用二分查找x所在的位置,此时是alls(x,l,r)排好序的,返回的坐标也会是按照x的大小所给出的;
int find(int x)
{
    int l=0,r=alls.size()-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1;//因为后续要使用前缀和,所以返回的坐标要加上1;
}

int main()
{
    int n,m;cin>>n>>m;
    //分别将要操作的四组数据记录在add和query中,将l,r,x的坐标值保存在alls中;
    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);
    }
    //将alls进行排序,并将重复的操作删除掉(如进行了两次在x的增值操作,应该去掉一个x保持平衡);
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    //一个迭代器从1开始直到末尾结束,itdm.first是x,second是r(在上方循环中可知);
    for(auto itdm : add)
    {
        int x;
        x=find(itdm.first);
        a[x]+=itdm.second;
    }
    //只循环x是因为x的坐标加上了值,而l,r可能有(l或r与x的值相同),且定义全局变量数组,其余值默认为0,故可以方便计算;
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];

    for(auto itdm : query)
    {
        int l,r;
        l=find(itdm.first);//找出l,r在a中的坐标
        r=find(itdm.second);
        printf("%d\n",s[r]-s[l-1]);//前缀和上方已计算,所以可直接输出,记得加上换行符!
    }
    return 0;
}

C语言版本

#include<stdio.h>
#include<stdlib.h>

#define n_Size 1000010
#define add_Size 10000
#define N 300010
//pair结构体
typedef struct PairNode {
    int first;
    int second;
}Pair;

typedef struct Vnode {
    Pair* data;
    int Size;
    int len;
}Array;
void InitArray(Array* A) {
    A->data = (Pair*)malloc(sizeof(Pair) * n_Size);
    A->len = 0;
    A->Size = n_Size;
    return;
}
//添加内存
void addSize(Array* A) {
    if (A->len < A->Size) return;
    A->data = (Pair*)realloc(A->data, A->Size + add_Size);
    A->Size += add_Size;
    return;
}
//添加元素
void Push(Array* A, int first, int second) {
    if (A->len >= A->Size) addSize(A);
    A->data[A->len].first = first;
    A->data[A->len].second = second;
    A->len++;
    return;
}

//排序
void sort(int* nums, int l, int r) {
    if (l >= r) return;
    int x = l;
    int i = l - 1, j = r + 1;
    while (i < j) {
        while (nums[++i] < nums[x]);
        while (nums[--j] > nums[x]);
        if (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    sort(nums, l, j);
    sort(nums, j + 1, r);
    return;
}
//去重
int unique(int* nums, int numsSize) {
    int i = 0, j = 0;
    while (j < numsSize)
    {
        if (nums[i] == nums[j]) j++;
        else nums[++i] = nums[j];
    }
    return i + 1;
}
//二分
int Findx(int* nums, int x, int numsSize) {
    int l = 0, r = numsSize - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int a[N] = { 0 }, s[N] = { 0 };
int alls[N];
int main() {
    int n, m;
    Array add, query;
    InitArray(&add);
    InitArray(&query);
    int alls_Size = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        int x, c;
        scanf("%d %d", &x, &c);
        Push(&add, x, c);
        alls[alls_Size++] = x;
    }

    for (int i = 0; i < m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        Push(&query, l, r);
        alls[alls_Size++] = l;
        alls[alls_Size++] = r;
    }

    sort(alls, 0, alls_Size - 1);
    alls_Size = unique(alls, alls_Size);


    for (int i = 0; i < add.len; i++) {
        int x = Findx(alls, add.data[i].first, alls_Size);
        a[x] += add.data[i].second;
    }

    //前缀和
    for (int i = 1; i <= alls_Size; i++)
        s[i] = s[i - 1] + a[i];

    //处理查询;

    for (int i = 0; i < query.len; i++) {

        int l = Findx(alls, query.data[i].first, alls_Size);
        int r = Findx(alls, query.data[i].second, alls_Size);
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}

本文链接:

https://nullcode.fun/164.html
1 + 3 =
快来做第一个评论的人吧~