离散化

离散化操作

两个使用到的函数：

1. C++ unique
   去重函数
   使用方法：unique (首地址，尾地址);
   功能：去除相邻的重复元素（只保留一个），并把重复的元素放在最后；
   unique 返回去重后的尾地址；

2. lower_bound() 函数，在前闭后开区间进行二分查找
   lower_bound() 是返回>=val 的位置，当所有元素都小于val，返回last位置；
   使用方法：lower_bound(首地址,尾地址,待查找元素val);

具体操作

一般情况下，我们离散化的话就是开一个结构体：

struct asd{
    int val;        //存入值
    int id;         //存入位置
};
asd q[N];
//然后按照val从小到大排序一下；
//再取一下：
for(int i=1;i<=n;i++)
    arr[q[i].id]=i;
//但是这样有一个点就是，如果是重复元素呢？
//比如1 2 3 3 4
//按照这样离散化以后就会变成：1 2 3 4 5
//然而我们可能有时候会需要重复元素离散化后的值是一样的，比如上述结果我是需要：1 2 3 3 4

//下面介绍一个这个离散化：
//先将输入元素存好，并再开一个vector（就叫xs吧）存入，然后将这个xs排序一下，然后利用 
// unique函数去重，最后for一遍，每次利用Lower_bound()查询到>=arr[i]的位置，
//复杂度O(nlogn);

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n;
int arr[N];
vector<int>xs;
void print()
{
    for(int i=1;i<=n;i++)
        printf("%d ",arr[i]);
    puts("");
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
        xs.push_back(arr[i]);
    }

    sort(xs.begin(),xs.end());
    auto e=unique(xs.begin(),xs.end());

    for(int i=1;i<=n;i++)
        arr[i]=lower_bound(xs.begin(),e,arr[i])-xs.begin()+1;
    print();
    return 0;
}