先列一下大纲？
- 第一天：各种基础容器
- 第二天：实现厉害一点的结构（半咕咕）
- 第三天：非变异算法和变异算法
**那么我们就开始吧！**
## Day1
【各种基础容器】
还是先列一下小目录
- vector
- deque
- list
- queue & stack
- priority_queue
- biset
- 集合 set
- 映射 map
#### 分类
种类 | 名称
-------- | -----
序列性容器 （可以用链表模拟的那种） | vector, deque, list
关联性容器 （可以用平衡树模拟的那种） | set, map, multiset, multimap
容器适配器（可以用数组模拟的那种） | stack, queue
基本每个容器都会有的又
#### 比较常用的函数
函数名 | 函数类型 | 意义
------|----- | -----
.empty() | bool | 没有元素返回true
.size() | int | 元素个数
.max_size() | int | 最大元素个数
= | operator | 将一个容器赋给另一个容器
swap | void | 交换两个容器的元素
.begin() | iterator | 返回第一个元素
.end() | iterator | 返回最后一个元素后面的元素
.erase(xxx) | void | 清除一个元素**或几个元素**
.clear() | void | 清空所有元素
#### 头文件要求
基本上都是 ``#include <容器名>``
好啦现在分别突破！
## vector & deque & list
#### 共有的函数
小声：我一直不知道insert函数返回的那个迭代器是什么。。
知道的大佬麻烦在评论指导一下qvq感恩不尽
另外我没写构造函数因为蒟蒻一般不用。。
函数名 | 函数类型 | 意义
------|----- | -----
.insert(iterator it, const T& x) | iterator | 在it所指那个元素前加一个x元素
.insert(iterator it, int n, const T& x) | void | 在it所指那个元素前加n个x元素
.insert(iterator it, const_iterator first, const_iterator end) | void | 在it所指那个元素前加入另一个同类型容器[first, last)之间的数据
.push_back(const T& x) | void | 尾部增加元素x
.push_front(const T& x) (只有deque，list可以用) | void | 首部增加元素x
.erase(iterator it) | iterator | 删除it所指元素
.erase(iterator first, iterator last) | iterator | 删除[first, last)之间的元素
.pop_back() | void | 容器不为空时，删除最后一个元素
.pop_front() （只有deque，list可以用）| void | 容器不为空时，删除第一个元素
.front() | reference（引用）| 首元素引用
.back() | reference | 尾元素引用
.assign(int n, const T& x) | void | 设置容器大小为n每个元素为x
.assign(const_iterator first, const_iterator last) | void | 设置容器有且只有[first, last)中的元素
deque，vector貌似没有什么别的常用操作了。。
但**list**还有好多、
函数名 | 函数类型 | 意义
------|----- | -----
.remove(const T& x) | void | 删除元素值等于x的元素
.sort() | void | 排序（默认升序）
.unique() | void | 去重
.reverse() | void | 反转顺序
.splice(iterator it, list& x) | void | 将x中所有元素**移入**当前list的it元素前
.splice(iterator it, list& x, iterator first) | void | 将x中[first, end)元素**移入**当前list的it元素前
.splice(iterator it, list& x, iterator first, iterator last) | void | 将x中[first, last)元素**移入**当前list的it元素前
.merge(list& x) | void | 将x与当前list合并（不同于splice的是， 两序列若各自升序，合并完还是升序）
需要注意的是
- 对任何位置的插入和删除 list永远是常数时间
- vector容量翻倍开，容易炸哦
- vector随机位置插入删除元素比较慢
- deque随机位置操作是**线性时间**
- list随机位置插入较快 但不支持随机访问
## stack & queue & priority_queue
这个大家都跟熟悉啦~
#### 共有的函数
函数名 | 函数类型 | 意义
------|----- | -----
.push(const T& x) | void | 插入元素（队尾or栈顶）
.pop() | void | 删除元素（队尾or栈顶）
各自的
- 队首`` .front()``
- 队尾`` .back()``
- 栈顶或优先队列堆顶 ``.top()``
返回值都是reference哦
## bitset 💗
哦天， 卡常大神器， 我爱了
它是一个二进制容器，可以看作一个巨大的二进制数
可以拿来做状压
它还有空间优化，每个元素一般只占1 bit，这是什么概念？
相当于一个char元素所占空间的八分之一
这篇博客我看了七八遍 orz胡小兔 [安利](https://www.cnblogs.com/RabbitHu/p/bitset.html)
所有的位运算可以对bitset直接操作
领养一只bitset：
bitset<位数> 名字；
#### bitset的常用函数
- 大小
``foo.size() ``返回大小（位数）
- 数1
``foo.count() ``返回1的个数
``foo.any() ``返回是否有1
``foo.none() ``返回是否没有1
- 赋值
``foo.set()`` 全都变成1
``foo.set(p)`` 将第p + 1位变成1
``foo.reset() ``全都变成0
``foo.reset(p)`` 将第p + 1位变成0
``foo.set(p, x) ``将第p + 1位变成x
- 取反
``foo.flip()`` 全都取反
``foo.flip(p)`` 将第p + 1位取反
- 转换
``foo.to_ulong()`` 返回它转换为unsigned long的结果，如果超出范围则报错
``foo.to_ullong()`` 返回它转换为unsigned long long的结果，如果超出范围则报错
``foo.to_string()`` 返回它转换为string的结果
## set & map & 它们的multi
set是集合（元素类型为Key）， map是映射（元素类型为pair<Key, Value>）, multi就是允许重复
#### 共有的函数
Key指key的类型， Value指value的类型
函数名 | 函数类型 | 意义
------|----- | -----
.insert(const T& x) | iterator或者pair<iterator, bool> | 插入x元素
.insert(iterator it, const T& x) | iterator | 在it所指处插入x元素
.insert(const_iterator first, const_iterator end) | void | 插入另一个同类型容器[first, last)之间的数据
.erase(const Key& key) | size_type(这是啥？) | 删除元素值（键值）等于key的元素（multiset和multimap删除的可能不止一个！）
.erase(iterator it) | iterator | 删除it所指元素
.erase(iterator first, iterator last) | iterator | 删除[first, last)之间的元素
.lower_bound(const Key& key) | const_iterator | 返回**大于等于**key的最小元素的指针，没有则返回end()
.upper_bound(const Key& key) | const_iterator | 返回**大于**key的最小元素的指针，没有则返回end()
.count(const Key& key) | int | 返回元素值（键值）等于key的元素个数
.equal_range(const Key& key) | pair<const_iterator, const_iterator> | 返回元素中等于key的迭代器指针[first, last)
.find(const Key& key) | const_iterator | 返回元素中等于key的迭代器指针
okk 今天就到这里吧 每天update哦~
最后安利一个比STL还STL noip还可以用！的[东西](https://baijiahao.baidu.com/s?id=1610302746201562113&wfr=spider&for=pc)
## Day2
- vector代替平衡树
luogu3369普通平衡树的代码
亲测
加上头文件一共26行
```cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int n;
vector<int> tree;
int main() {
int x, opt;
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%d%d", &opt, &x);
int pos = lower_bound(tree.begin(), tree.end(), x) - tree.begin();
switch(opt){
case 1: tree.insert(tree.begin() + pos, x); break;
case 2: tree.erase(tree.begin() + pos, tree.begin() + pos + 1); break;
case 3: printf("%d\n", pos + 1); break;
case 4: printf("%d\n", tree[x - 1]); break;//注意这里是x-1哦
case 5: printf("%d\n", tree[pos - 1]); break;
case 6: printf("%d\n", *upper_bound(tree.begin(), tree.end(), x)); break;
}
}
return 0;
}
```
但是有这么个小问题
这些容器 好像都维护不了区间和欸。。
又切了几道题 就算Day2吧
### pbds的平衡树
这里仅陈列pbds平衡树常用用法
参考[博客]()
包含：ext/pb_ds/assoc_container.hpp和ext/pb_ds/tree_policy.hpp
声明：__gnu_pbds::tree
typename Key , typename Mapped ,
typename Cmp_Fn = std :: less <Key >,
typename Tag = rb_tree_tag ,
template <
typename Const_Node_Iterator ,
typename Node_Iterator ,
typename Cmp_Fn_ , typename Allocator_ >
class Node_Update = null_tree_node_update ,
typename Allocator = std :: allocator <char > >
class tree ;
注：如果有第二优先排序的话，用pair（先拍first）
过于常见：
- .begin()
- .end()
- .size()
- .empty()
- .clear()
常见：
- .begin() 最小值
- .end() 最大值后一位
- .find_by_order（val）返回迭代器 第val个数
- .order_of_key(val) 返回值 比他小的数有多少个
- .find(const Key)
- .lower_bound(const Key) 返回迭代器
- .upper_bound(const Key)返回迭代器
- .erase(iterator)
- .erase(const Key)
- .insert(const pair<> )
- .operator[]
- void join(tree &other) 把other中所有元素移动到*this上（值域不能相交，否则抛出异常。
- void split(const_key_reference r_key, tree &other) 清空other，然后把*this中所有大于r_key的元素移动到other。
- get_l_child和get_r_child 左右儿子
自定义update:
```cpp
template < class Node_CItr , class Node_Itr ,
class Cmp_Fn , class _Alloc >
struct my_node_update {
virtual Node_CItr node_begin () const = 0;
virtual Node_CItr node_end () const = 0;
typedef int metadata_type ;
inline void operator ()( Node_Itr it , Node_CItr end_it ){
Node_Itr l = it. get_l_child (), r = it. get_r_child ();
int left = 0, right = 0;
if(l != end_it ) left = l. get_metadata ();
if(r != end_it ) right = r. get_metadata ();
const_cast < metadata_type &>( it. get_metadata ())
= left + right + (* it)-> second ;
}
inline int prefix_sum (int x) {
int ans = 0;
Node_CItr it = node_begin ();
while (it != node_end ()) {
Node_CItr l = it. get_l_child (), r = it. get_r_child ();
if( Cmp_Fn ()(x, (* it)-> first )) it = l;
else {
ans += (* it)-> second ;
if(l != node_end ()) ans += l. get_metadata ();
it = r;
}
}
return ans;
}
inline int interval_sum (int l, int r){
return prefix_sum (r) - prefix_sum (l - 1);
}
}
int main() {
tree <int , int , std :: less <int >, rb_tree_tag , my_node_update > T;
T [2] = 100; T [3] = 1000; T [4] = 10000;
printf ("%d\n", T. interval_sum (3, 4));
printf ("%d\n", T. prefix_sum (3));
}
```
## Day3
#### 非变异算法与变异算法
分为循环，查询，计数，比较四类
复杂度是线性的，感觉用不太上，简单看看就好啦。。
[转自](https://blog.csdn.net/u014634338/article/details/38095803)
网友评论