离散化

例如一共有 ${10}^5$ 个数，但是数的值域很大 ${10}^9$，而有的时候我们需要把这些数的值作为数组下标，难道我们要开一个 ${10}^9$ 大小的数组吗？

答案当然是否定的，我们此时需要将 $0\sim {10}^9$ 映射到 $0\sim {10}^5$ 上去。

1, 3, 100, 200, 500000, ...
-->
1, 2, 3,   4,   5,      ...

离散化需要注意的问题：

• 待离散化的数组 a[] 中可能存在重复元素：需要去重
• 我们需要快速映射，如何快速计算 a[i] 离散化后的值
  • 显然我们只需要把 a[i] 放到数组中，离散化后的值就是 i
  • 此时对于某个在 a 数组中的数 x，找到它的下标就要用二分
• 我们需要 保序离散化

核心代码：

vector<int> alls;
sort(alls.begin(), alls.end());
all.erase(unique(alls.begin(), alls.end()), alls.end());

其中：

• unique(a.begin(), a.end()); 返回去重操作后 a 中重复元素开始的位置
• 例如 1 2 2 3 4 去重后就是 1 2 3 4 2，返回 a[4] 对应的迭代器
• a.erase(iter, a.end()); 擦除后面的重复元素，得到无重复元素的数组

二分搜索求出 x 对应的离散化值：

int find(int x) {
    int l = 0;
    int r = alls.size() - 1;

    while (l < r) {
        int mid = l + r >> 1;
        // find first >= x
        if (alls[mid] >= x) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }

    return r + 1; // map to 1~n
}

这里可以看出：离散化说白了就是找到 x 在 alls 中从小到大排第几位（所以要返回 r + 1）

区间和

AC802. 区间和

如果数据下标范围比较小，其实就是 前缀和算法，将数轴上所有位置分配到数组中去。

虽然数轴长 $2\times {10}^9$，但是只有 $n$ 次操作加上 $2m$ 次左右端点询问，因此最多只会取到其中的 $n+2m$ 个坐标。

核心代码：

// ...
    // deduplicate
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()), alls.end());

    // insert
    for (auto t : add) {
        int x = find(t.first);
        a[x] += t.second;
    }

    // prefix sum
    for (int i = 1; i <= alls.size(); i ++) {
        s[i] = s[i - 1] + a[i];
    }

    // query
    for (auto t : query) {
        int l = find(t.first);
        int r = find(t.second);

        cout << s[r] - s[l - 1] << endl;
    }

区间合并

AC803. 区间合并

由图可知：

• 将所有区间按照区间的左端点大小排序，区间起点和终点分别用 st[], ed[] 存储
• 扫描所有区间，对于当前区间 i，它之后的区间 j 与它的关系有以下三种：
  • st[i] <= st[j], ed[j] <= ed[i] 当前区间完全包含后者（可以合并）
  • st[i] <= st[j] <= ed[i] < ed[j] 二者有重叠部分（可以合并）
  • st[i] < ed[i] < st[j] < ed[j] 二者没有重叠部分（不可合并）
  • 不会出现下图中红色的情况

对于以上两种情况的合并方式为：

• 第一种：不动
• 第二种：ed[i] = ed[j] 即可
• 直到当前区间 i 与后面的区间没有任何交集，说明枚举完毕

合并核心算法：

void merge(vector<PII> &segs) {
    sort(segs.begin(), segs.end());  // left first

    int st = -2e9;
    int ed = -2e9;

    for (auto seg : segs) {
        if (ed < seg.first) {  // find new seg
            if (st != -2e9) {
                res.push_back({st, ed});
            }

            st = seg.first;
            ed = seg.second;
        }
        else {
            ed = max(ed, seg.second);
        }
    }

    if (st != -2e9) { // input is not empty
        res.push_back({st, ed});
    }
}

二维区间合并

AC759. 格子染色

操作符重载，使得 sort 可以正确排序。

struct Node {
    int idx;
    int st, ed;

    bool operator < (const Node& t) const {
        if (idx != t.idx) {
            return idx < t.idx;
        }
        else if (st != t.st) {
            return st < t.st;
        }
        else {
            return ed < t.ed;
        }
    }
};