离散化 - 洛谷保存站

## 离散化
### 定义
>通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化。——oiwiki

### 方法
1. 建立原数组的副本
2. 将副本排序
3. 去重
4. 以该数在副本中的下标代替原数组中的数

代码实现：
```cpp
for(int i = 1; i <= n; i++)
    b[i] = a[i];
sort(b + 1, b + 1 + n);
int len = unique(b + 1, b + 1 + n) - b - 1;
for(int i = 1; i <= n; i++) 
    a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
```
总时间复杂度 $O(n\ logn)$

其中 `unique` 函数的功能是将数组中相邻的重复元素去除。然而其本质是将重复的元素移动到数组的末尾，最后再将迭代器指向第一个重复元素的下标。  
`unique` 函数的时间复杂度为 $O(n)$

### 例题
#### [P1496火烧赤壁](https://www.luogu.com.cn/problem/P1496)

__离散化+差分__

简化题意后发现可以直接模拟，每次给区间 $[l,r]$ 中的数变成 $1$，最后统计 $1$ 的个数  
由于数据范围很大，直接模拟肯定不可行，故离散化后进行差分，最后求前缀和

统计时即统计离散化前每个不为 $0$ 的区间长度，求出每个区间离散化后的左端点与右端点，然后显而易见 `b[l]` 为离散化前的左端点， `b[j]` 为离散化前的右端点

```cpp
#include<bits/stdc++.h>
#define itn int
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define int ll

using namespace std;

const int maxn = 4e4 + 10;

struct node{
    int l, r, nl, nr;
}a[maxn];

int n;
int b[maxn], s[maxn], sum[maxn];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].l >> a[i].r;
        b[i] = a[i].l, b[n + i] = a[i].r;
    }
    sort(b + 1, b + 1 + n * 2);
    int len = unique(b + 1, b + 1 + n * 2) - b - 1;
    for(int i = 1; i <= n; i++){
        a[i].nl = lower_bound(b + 1, b + 1 + len, a[i].l) - b;
        a[i].nr = lower_bound(b + 1, b + 1 + len, a[i].r) - b;
    }
    for(int i = 1; i <= n; i++){
        s[a[i].nl + 1]++;
        s[a[i].nr + 1]--;
    }
    for(int i = 1; i <= len; i++)
        sum[i] +=(sum[i - 1] + s[i]);
    int l ,r ,ans = 0;
    for(int i = 1; i <= len; i++){
        if(sum[i] != 0 && sum[i - 1] == 0) l = i - 1;
        if(sum[i] != 0 && sum[i + 1] == 0){
            r = i;
            ans += b[r] - b[l];
        }
    }
    cout << ans << endl;
    return 0;
} 
```

正在渲染内容...