33DAI：批量导入三三文档

2026-05-20T18:24:02Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第58行：		第58行：
	[[Category:进阶算法]]		[[Category:进阶算法]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:17Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 离散化 ==

离散化将'''很大但数量很少'''的值映射到较小的连续整数，常用于权值数组、线段树等场景。

=== 基本方法 ===

<syntaxhighlight lang="cpp">
vector<int> a = {100, 99999, 5, 100, 5}; // 原始数据
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end()); // 去重

// 查询 x 离散化后的值（0-indexed）
auto get_id = [&](int x) -> int
{
return lower_bound(b.begin(), b.end(), x) - b.begin();
};

// a 离散化后: {1, 2, 0, 1, 0}
</syntaxhighlight>

=== 手动离散化模板 ===

<syntaxhighlight lang="cpp">
struct Discrete
{
int n;
vector<int> val;
Discrete(const vector<int>& a)
{
val = a;
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
n = val.size() - 1; // 1-indexed
}

// 查询 x 的排名（1-indexed）
int id(int x)
{
return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}

// 恢复原始值
int val_of(int id)
{
return val[id - 1];
}
};
</syntaxhighlight>

=== 应用场景 ===

* 权值线段树 / 树状数组（值域很大时先离散化）
* 扫描线算法
* 区间覆盖问题

[[Category:进阶算法]]
[[Category:三三文档]]

09-进阶算法/05-离散化 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档