离散化

什么事离散化？

离散化的本质是将已知序列建立新的下标索引，最终来缩小目标区间，并且可以结合二分，前缀和等算法进行额外的操作

离散化需要进行排序去重

1. 排序：sort(alls.begin(),alls.end())
2. 去重：alls.earse(unique(alls.begin(),alls.end()),alls.end());

unque函数实现

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];
				}
		}
		
		return a.begin() + j;
}

离散化常见题目

给定一个无限长的数轴

输入一个n，执行n次操作即在x的位置上插入一个数c

输入一个m，执行m次操作，每一次操作给出两个数l和r，代表数轴的左右端点

最终打印l和r之间的区间总和

定义数组大小，由于我们插入操作包含在指定下标插入，插入左右端点，所以需要定义N = 300010

我们需要定义三个集合，一个集合用来统计下标，其余两个集合用来对插入的数据进行存储

find函数，由于我们离散化的本质就是通过集合从0开始建立下标代替原本插入值的下标，我们可以通过插入的x找到在集合中的位置，在对应的位置上 += 它的值

接着求数组的前缀和

最终通过a[r] - a[l - 1]求区间和

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 300010;
vector<int> alls;
vector<PII> a,b;
int tmp[N],s[N];
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(){
    int n,m;
    cin >> n >> m;
    while(n--) {
        int x,c;
        cin >> x >> c;
        a.push_back({x,c});
        alls.push_back(x);
    }
    
    while(m--) {
        int l,r;
        cin >> l >> r;
        b.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    
    
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    for(auto it : a) {
        int t = find(it.first);
        tmp[t] += it.second;
    }
    
    for(int i = 1;i <= alls.size();i++) s[i] = s[i - 1] + tmp[i];
    
    for(auto it : b) {
        int rl = find(it.first),rr = find(it.second);
        cout << s[rr] - s[rl - 1] << endl;
    }
    
    return 0;
}