multiset

#multiset##牛客AI配图神器#

`multiset` 是 C++ 标准库中的一个关联容器，位于 `<set>` 头文件中。它与 `set` 类似，但**允许存储重复的元素**，且内部始终保持有序（默认升序）。

---

 1. 基本定义
```cpp
#include <set>
using namespace std;

multiset<int> ms;                 // 升序（默认）
multiset<int, greater<int>> ms2;  // 降序
```

---

2. 常用操作
| 操作 | 代码示例 | 说明 |
|------|----------|------|
| 插入 | `ms.insert(x);` | 插入一个元素，允许重复 |
| 查找 | `auto it = ms.find(x);` | 返回第一个等于 `x` 的迭代器，找不到返回 `end()` |
| 计数 | `int cnt = ms.count(x);` | 返回 `x` 出现的次数 |
| 删除单个 | `ms.erase(it);` | 删除迭代器指向的元素 |
| 删除所有 | `ms.erase(x);` | 删除所有等于 `x` 的元素 |
| 大小 | `int sz = ms.size();` | 当前元素个数 |
| 清空 | `ms.clear();` | 删除所有元素 |

---

 3. 边界迭代器（重要）
- **`lower_bound(x)`**：返回第一个 **≥ x** 的迭代器。
- **`upper_bound(x)`**：返回第一个 **> x** 的迭代器。
- **`begin()`**：指向第一个元素（最小）。
- **`end()`**：指向最后一个元素**之后**的位置（不指向实际元素）。

**注意**：
- 当所有元素都小于 `x` 时，`lower_bound(x)` 返回 `end()`。
- 当容器为空时，`begin() == end()`。

---

 4. 迭代器与距离
迭代器可以像指针一样移动和取值：
```cpp
auto it = ms.begin();      // 指向第一个元素
int first = *it;           // 获取元素值
++it;                      // 移动到下一个元素
```

**`distance(begin, it)`**：计算两个迭代器之间的元素个数（需要 `<iterator>` 头文件）。  
例如：统计左边小于当前值的元素个数：
```cpp
auto it = ms.lower_bound(x);
int less_cnt = distance(ms.begin(), it);   // 比 x 小的元素个数
```
- 当 `it == ms.end()` 时，`distance` 等于当前总个数（所有元素都小于 `x`）。

---

 5. 与 `set` 的区别
| 特性 | `set` | `multiset` |
|------|-------|------------|
| 重复元素 | 不允许 | 允许 |
| 插入 | 唯一 | 可重复 |
| 删除 `erase(value)` | 最多删一个 | 删所有相等的 |
| 常用场景 | 需要唯一集合 | 需要计数或保留重复值 |

---

 6. 时间复杂度
- 插入、删除、查找、`lower_bound` / `upper_bound`：**O(log n)**
- 遍历（如 `for` 循环）：O(n)
- `distance` 在非随机访问迭代器上是 O(k)，k 为距离，**不是 O(1)**。

---

7. 实际应用：统计左边比当前小的元素个数（经典题）
```cpp
#include <iostream>
#include <set>
#include <iterator>
using namespace std;

int main() {
    int n, x;
    cin >> n;
    multiset<int> left;   // 存放左边已出现的数

    for (int i = 0; i < n; ++i) {
        cin >> x;
        auto it = left.lower_bound(x);          // 第一个 >= x 的位置
        int cnt = distance(left.begin(), it);   // 左边 < x 的个数
        cout << cnt << " ";
        left.insert(x);
    }
    return 0;
}
```

**解释**：  
- 因为 `left` 有序，所有小于 `x` 的元素都在 `begin()` 到 `it` 之间。  
- `lower_bound` 返回第一个 ≥ x 的位置，正好划出了“小于 x”的区间。  
- 使用 `distance` 得到区间长度，即小于 `x` 的个数。  
- 每次遍历后把当前值插入，供后续比较。

---

 8. 为什么不用 `set`？
`set` 会去重，如果左边有重复的可爱值，统计结果会偏小，而 `multiset` 保留了所有重复值，保证计数正确。

---
 9. 注意事项
- 包含头文件 `<set>`，使用迭代器时可能需要 `<iterator>`（`distance` 在其中）。
- 不要解引用 `end()`，也不要在空容器上解引用 `begin()`。
- 当使用 `auto` 时，编译器自动推导迭代器类型，简化代码。

---

 10. 总结
`multiset` 是一个**有序可重复容器**，适合需要维护动态有序序列且允许重复的场景。通过 `lower_bound` 和 `distance` 可以轻松统计比当前元素小的个数，是解决“左边比当前小”类问题的利器。掌握它的基本操作，可以让你在处理有序数据时更加得心应手。