2026/2/24
* 1.MAP:
* (1).定义MAP：
* 导入：#include <map>
* 定义：map<建的类型，值的类型> 名字;
* 如：map<int,int> m;
* (2). MAP相关操作：
函数 功能说明 begin() 返回一个迭代器，指向map中的第一个键值对。 end() 返回一个迭代器，指向map中最后一个键值对的下一个位置。 erase() 根据键删除一个键值对。 clear() 清空map中的所有键值对 empty() 如果map为空则返回true size() 返回map中键值对的数量 find() 查找一个键是否存在于map中，如果找到了则返回该键对应的迭代器，否则返回map::end() swap() 交换两个map rbegin() 返回一个指向map尾部的逆向迭代器 rend() 返回一个指向map头部的逆向迭代器 count()
返回指定元素出现的次数 max_size() 返回可以容纳的最大元素个数 insert() 插入元素 key_comp() 返回比较元素key的函数 value_comp() 返回比较元素value的函数
* (3). MAP的两种遍历方式：
* 2.SET
* (1).定义SET：
* 导入：#include <set>
* 定义：set<类型> 名字;
* 如：set<int> s;
* (2).SET的相关操作
函数 功能说明 begin() 返回一个迭代器，指向集合中的第一个元素（std::set 为有序首元素，std::unordered_set 为哈希表首个存储元素）。 end() 返回一个迭代器，指向集合中最后一个元素的下一个位置（尾后迭代器，不可解引用）。 erase() 可按值、迭代器或迭代器范围删除集合中的元素，按值删除时返回删除的元素个数（0 或 1）。 clear() 清空集合中的所有元素，清空后集合大小为 0。 empty() 如果集合为空则返回 true，否则返回 false。 size() 返回集合中当前存储的元素个数。 find()
查找指定值的元素，找到则返回该元素的迭代器，未找到则返回 end()。 swap() 交换两个同类型集合的内容（元素、大小等），效率高。 rbegin() 返回指向集合尾部的逆向迭代器（仅 std::set 支持，unordered_set 无逆向迭代器）。 rend() 返回指向集合头部的逆向迭代器（仅 std::set 支持，unordered_set 无逆向迭代器）。 count() 返回集合中指定值的元素出现次数（集合元素唯一，故返回值为 0 或 1）。 max_size() 返回集合理论上可容纳的最大元素个数（受系统内存、编译器限制）。 insert()
插入单个元素或元素范围，插入重复元素时会失败，返回 pair<迭代器, bool> 标识结果。 key_comp() 返回用于比较集合元素（键）的比较函数对象（仅 std::set 支持，unordered_set 无此函数）。 value_comp() 返回用于比较集合元素（值）的比较函数对象（仅 std::set 支持，unordered_set 无此函数）。 emplace() 直接在集合中构造元素（避免拷贝/移动），效率比 insert() 更高，返回值同 insert()。 emplace_hint() 结合迭代器提示插入元素（仅 std::set
有优化效果），进一步提升插入效率。 bucket_count() 返回哈希表的桶数量（仅 std::unordered_set 支持，std::set 无此函数）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2026/2/25
* 1.DEQUE
* (1).定义DEQUE：
* 导入：#include <deque>
* 定义：deque<类型> 队列名;
* 如： deque<int> q;
* (2).DEQUE的操作：
* 2.LIST
* (1).定义LIST：
* 导入：#include <list>
* 定义：list<类型> 链表名;
* 如： list<int> L;
* 3.PAIR
* (1).定义PAIR：
* 导入：#include <utility>
* 定义：pair<类型,类型> 变量名;
* 如： pair<int,int> p;
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2026/6/6
* 1.ST表
* (1). ST表的数据结构定义：
* dpi][j]dpi][j]dpi][j]表示左端点为iii，右端点为i+2j−1i + 2^{j-1}i+2j−1，区间长度为2j2^j2j的区间最值。递推关系为：
dp[i][j]=max(dp[i][j−1],dp[i+1<<(j−1)][j−1])dp[i][j] = max(dp[i][j - 1],dp[i + 1 << (j - 1)][j - 1]) dp[i][j]=max(dp[i][j−1],dp[i+1<<(j−1)][j−1])
其中1<<(j−1)1 << (j - 1)1<<(j−1)表示2j−12^{j - 1}2j−1
* (2). ST表的相关代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2026/6/13
* 1.线段树
* (1).如何建树：
* (2).单点修改：
* (3).区间查询：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2026/6/20
* 1.线段树
* (1).懒标记以及区间修改：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2026/7/4
* 1.树状数组：
* (1).LOWBIT：
* lowbitlowbitlowbit函数是帮助我们找到二进制表达式中最低位 111 所对应的值
* (2).单点修改：
* (3).区间求和：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2026/7/4
* 1.字典树
* (1).插入
* (2).查找
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2026/8/8
* 1.四边形不等式优化:
* 在区间动态规划中，对递推关系如
Bi,j={0,i=ji<k≤jmin{Bi,k−1+Bk,j}+w(i,j),i<jB_{i, j} = \begin{cases} 0, i = j\\ {}^{min}_{i < k \le j} \text\{B_{i, k - 1} + B_{k, j}\} + w(i, j), i < j \end{cases} Bi,j ={0,i=ji<k≤jmin {Bi,k−1 +Bk,j }+w(i,j),i<j
令
KB(i,j)=min{k:Bi,j=Bi,k−1+Bk,j+w(i,j)}K_B(i, j) = min\{k : B_{i, j} = B_{i, k - 1} + B_{k, j} + w(i, j)\} KB (i,j)=min{k:Bi,j =Bi,k−1 +Bk,j +w(i,j)}
即 KB(i,j)K_B(i, j)KB (i,j) 为区间 [i,j][i, j][i,j] 的最佳决策点（使得 Bi,jB_{i, j}Bi,j 取最小值的下标 kkk），可以证明一下两个结论：
1. 如果 www 满足子变形不等式和区间包含单调性，则具有代价函数 BBB 亦满足四边形不等式
2. 当结论 111 成立时，有 KB(i,j−1)≤KB(i,j)≤KB(i+1,j),i≤jK_B(i, j - 1) \le K_B(i, j) \le K_B(i + 1, j), i \le jKB (i,j−1)≤KB (i,j)≤KB (i+1,j),i≤j
应用四边形不等式优化的步骤时首先证明 www 满足四边形不等式和区间包含单调性
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2026/8/9
* 乘法逆元：
* 求 aia_iai 的逆元
定义 sis_isi 为 aia_iai 的前缀积
先求 sis_isi 的逆元，由于 1si=1si+1×ai+1\frac{1} {s_i} = \frac {1}{s_{i + 1}} \times a_{i + 1}si 1 =si+1 1 ×ai+1 ，所以先求出 1sn\frac{1} {s_n}sn 1 即可递推
再由 1ai=1si×si−1\frac{1} {a_i} = \frac {1}{s_i} \times s_{i - 1}ai 1 =si 1 ×si−1 求出 aia_iai 的逆元
