前言

离散化用途广泛，很多时候数的区间很大，而数据量却很少，这时可以使用离散化的操作。离散化是一种类似哈希的思想，这里总结三种离散化方式(C++语言)，包括保序和非保序离散化，保留绝对关系和保留相对关系的离散化。

一. 保序且保留绝对关系

这种离散化的方式实质是：压缩空间。

这种离散化方式借助C++ STL：sort + vector + unique + erase + lower_bound（排序、动态数组、unique、erase、二分查找）

1. unique

查阅相关资料后，unique函数将相邻的相同元素放置于数组最后，并没有改变数组的大小。因此需要先进行排序，以保证去重。

unique返回的是容器末尾,可以求出容器的size。与lower_bound稍微有点不同。（注意后面）
lower_bound不论下标从0还是从1开始：

pos=lower_bound(b + 1,b + sz + 1,a[i]) - b;
pos=lower_bound(b ,b + sz,a[i]) - b;

而unique求容器的size：

sz = unique(b + 1,b + n + 1) - (b + 1);
sz = unique(b,b + n) - b;

unique(v.begin(),v.end())

2. erase

erase(it1,it2):删除it1到it2之间的所有元素

v.erase(unique(v.begin(),v.end()),v.end());

3. 注意lower_bound的使用，下标要+1（大多数情况）

cout << "离散化后200的位置为：" << lower_bound(v.begin(),v.end(),200) - v.begin() + 1 << endl;

4. 离散化模板

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

5. 练习

例题：区间和

注意数组的大小，注释中有。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> alls;
vector<pair<int,int> > add,query;
int a[300010],s[300010];                 // 注意是300010，添加1个下标，查询2个下标，加起来一个三个下标.

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    
    while(n--){
        int x,c;
        scanf("%d%d",&x,&c);
        
        alls.push_back(x);
        add.push_back({x,c});
    }
    
    while(m--){
        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(int i=0;i<(int)add.size();i++){
        int x = add[i].first;
        int c = add[i].second;
        int pos = lower_bound(alls.begin(),alls.end(),x)-alls.begin();
        pos ++;        // 下标从1开始.
        
        a[pos] += c;
    }
    
    for(int i=1;i<=(int)alls.size();i++)  s[i] = s[i-1] + a[i];
    
    for(int i=0;i<(int)query.size();i++){
        int l = query[i].first;
        int r = query[i].second;
        
        int pos1 = lower_bound(alls.begin(),alls.end(),l)-alls.begin();
        int pos2 = lower_bound(alls.begin(),alls.end(),r)-alls.begin();
        pos1++;
        pos2++;
        
        printf("%d\n",s[pos2]-s[pos1-1]);
    }
    
    return 0;
}

二.保序且保留相对关系

借助辅助数组，保留相对关系。如1 2 5 离散化后为 1 2 3.

注：这里借助的 pair<int,int> ，当然也可以借助结构体去实现。

	int n = 3;
	pair<int,int> b[15];
	int c[15];
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i].first);
		b[i].second = i;
	}
	sort(b+1,b+n+1);
	
	int pos = 1;
	for(int i=1;i<=n;i++){
		if(b[i].first!=b[i-1].first && i!=1)	pos++;
		
		c[b[i].second] = pos;
	}
	
	for(int i=1;i<=n;i++)		cout << c[i] << " ";
	cout << endl;

三.不保序只保存元素

这种离散化方式借助map或者set去储存出现的元素。

借助set：

	set<int> s;
	n = 5;
	int x;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		s.insert(x);
	}
	
	for(auto p:s){
		cout << p << " ";
	} 
	cout << endl;

借助map：

	map<int,int> mp;
	n = 5;
	int x;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		mp[x] = 1;
	}
	
	for(auto p:mp){
		cout << p.first << " ";
	}
	cout << endl;