前三个只讲STL(都1202年了不会还有人在手写吧……)
栈
FILO(First In Last Out)，实现方法就是模拟
std::stack<TypeName> s; // 使用默认底层容器 deque，数据类型为 TypeName
std::stack<TypeName,Container> s; // 使用 Container 作为底层容器
std::stack<TypeName> s2(s1);
s.top();//取顶部元素
s.push(x);//把x从顶部入栈
s.pop();//弹出顶部元素
s.size();//返回容器中元素数量
s.empty();//查询容器是否为空
队列
FIFO(First In First Out)，同上
std::queue<TypeName> q; // 使用默认底层容器 deque，数据类型为 TypeName
std::queue<TypeName, Container> q; // 使用 Container 作为底层容器
std::queue<TypeName> q2(q1); // 将 s1 复制一份用于构造 q2
q.front();//取顶部元素（此时队列不能为空）
q.push(x);//把x从顶部入队
q.pop();//弹出顶部元素
q.size();//返回容器中元素数量
q.empty();//查询容器是否为空
堆
std::priority_queue<TypeName> q; // 数据类型为 TypeName
std::priority_queue<TypeName,Container> q; // 使用 Container 作为底层容器
std::priority_queue<TypeName,Container,Compare> q;//Compare是比较器，用greater<int>是小根堆，用less<int>是大根堆
auto cmp = [](const std::pair<int,int> &l， const std::pair<int， int> &r) {
return l.second < r.second;
};
std::priority_queue<std::pair<int,int>， std::vector<std::pair<int,int> >，decltype(cmp)>//自定义比较器的写法，decltype是为了查询表达式的数据类型(cmp开的auto)
q.push(x);//访问堆顶元素（此时优先队列不能为空）
q.empty();//查询容器是否为空
q.size();//查询容器中的元素数量
-----以上操作为常数复杂度-----
q.push(x);//插入元素，并对底层容器排序
q.pop();//删除堆顶元素（此时优先队列不能为空）
-----以上操作为log复杂度-----
上面三种数据结构用的STL都属于容器适配器，它们使用的默认底层容器是双端队列deque(队列和栈)和向量vector(优先队列)，因此对他们使用容器本身支持的操作也是可行的，但是复杂度也相应的是底层容器的复杂度，下方对这两种底层容器进行简单介绍
deque
vector
vector<int> v;//新建vector
v.reserve(3);//预分配3个元素的空间
vector<int> v(3);//创建vector并预分配空间
vector<int> v(3, 2);//创建vector,预分配空间并赋初值为2
vector<int> v(v2);//新建v拷贝v2至v
vector<int> v(v2.begin() + 1, v2.begin() + 3);//新建v并拷贝v2[1..3]至v
vector<int> v(std::move(v2)); //新建v并把v2移动到v
v.push_back()//从末尾插入
v.pop_back()//删除末尾
v.insert()//在特定位置插入元素,是线性复杂度的,与目的位置离末尾的距离有关
v.size()//返回容器中已经被占用的大小,v.capcity()返回的是在不扩容的情况下的容量上限
v.clear();//清空
并查集
fa[i] = i;
int find(int x){
if(fa[x] != x){
fa[x] = find(fa[x]);//路径压缩
}
return fa[x];
}
int find(int x){//无路径压缩
if(fa[x] == x) return x;
return find(fa[x]);
}
void merge(int x，int y){
int X = find(x);
int Y = find(Y);
if(X == Y) return;
fa[X] = Y;//如果用按秩合并就把size小的合并到size大的，记得合并size
}种类并查集
有时候我们需要维护的信息中存在不同集合之间的关系，那么原先只维护一个集合的并查集就不再适用了，这时，我们可以通过将fa数组分段的方式实现基于关系维护集合。以NOI 2001食物链为例
int c[maxn * 3];//[1,n]为A,[n + 1,2n]为B,[2n + 1,3n]为C
if(tmp==1){
if(find(x + n) == find(y) || find(x) == find(y + n)){
ans++;
}else{
merge(x,y);
merge(x + n,y + n);
merge(x + n * 2,y + n * 2);
}
}else{
if(find(x) == find(y) || find(x) == find(y + n)){
ans++;
}else{
merge(x + n,y);
merge(x + n * 2,y + n);
merge(x,y + n * 2);
}
}题目中设定了三个存在捕食与被捕食关系的种群，我们用一个3倍maxn大的fa数组同时进行维护，因为输入不会提供生物个体所属的种群，所以我们可以在三个种群中同时标示两种生物属于同一个种群，给每个生物在每个集合中都创造一个”分身”，而捕食关系则可以表示为捕食者与被捕食者在能捕食它的集合中的”分身”属于同一个集合
单调栈
维护一个单调的栈来优化一些原本需要扫一遍的最值问题，例题POJ3250，比单调队列那个简单（doge
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <cctype>
#define int long long
using namespace std;
template <typename T> inline T read(){
T sum = 0;
int fl = 1，ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}
const int maxn = 8e4 + 5;
int n;
int a[maxn];
stack <int> s;
signed main(){
n = read<int>();
for(int i = 1; i <= n; i++){
a[i] = read<int>();
}
int ans = 0;
for(int i = 1; i <= n; i++){
while(!s.empty() && s.top() <= a[i]) s.pop();
if(!s.empty() && s.top() > a[i]) ans += s.size();
s.push(a[i]);
}
printf("%lld\n"，ans);
return 0;
}单调队列
顾名思义就是维护一个单调的队列(deque)来优化一些原本需要扫一遍的最值问题。
以滑动窗口为例，我们需要求每连续k个数中的最值，暴力显然需要O(k(n-k))次，是n^2级别的。考虑对它进行优化，显然，对于第一个区间，从头扫到尾才能知道它的最大值，但是在移动查询区间时，就有优化的空间了。不难想到，当查询区间往右边移动一个时，如果当前的最大值在移动后仍然在查询区间内，并且新加入区间的数比当前的最大值大，那么新加入区间的数一定为此区间中的最大值，否则区间中的最大值不变。如果当前的最大值在移动后不在查询区间内，新加入的数会是新的最大值吗？答案显然是不一定。正因为如此，我们才会在每个查询区间内维护一个单调递减的序列，这样，每次弹出查询区间外的值后，留下的队头就是不考虑新加入查询区间的数时的最大值，我们将它与新加入区间的数进行比较就能得知当前的区间最大值
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <deque>
#include <cctype>
using namespace std;
template <typename T> inline T read(){
T sum = 0;
int fl = 1，ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}
inline void write(int x){
if(x < 0){
x = -x;
putchar('-');
}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 1e6 + 5;
int n，k;
int a[maxn];
deque < pair<int，int> > q;
int main(){
n = read<int>();
k = read<int>();
for(int i = 1; i <= n; i++){
a[i] = read<int>();
}
for(int i = 1; i <= n; i++){
while(!q.empty() && q.front().first <= i - k) q.pop_front();//如果当前最小值不在查找范围内，弹出
while(!q.empty() && q.front().second >= a[i]) q.pop_front();//如果当前队头不是最大值，弹出
while(!q.empty() && q.back().second >= a[i]) q.pop_back();//如果队列不单调，弹出(查找范围内不单调则不可能为答案)
q.push_back(make_pair(i，a[i]));
if(i >= k) write(q.front().second)，putchar(' ');
}
puts("");
q.clear();
for(int i = 1; i <= n; i++){
while(!q.empty() && q.front().first <= i - k) q.pop_front();
while(!q.empty() && q.front().second <= a[i]) q.pop_front();
while(!q.empty() && q.back().second <= a[i]) q.pop_back();
q.push_back(make_pair(i，a[i]));
if(i >= k) write(q.front().second)，putchar(' ');
}
return 0;
}树状数组
也是一种用分治的思想维护区间的方式，不过不像线段树结点维护的区间长度从上到下折半，树状数组的结点维护区间的方式是通过lowbit，编号为n的结点维护n及n之前共lowbit(n)个结点
inline int lowbit(int x){
return x&-x;
}
int query(int i){//前i位的和,若区间[l,r]的和等于区间[1,r]的和减去区间[1,l-1]的和
int tmp = 0;
for(; i; i -= lowbit(i)) tmp += c[i];//由上述结点维护区间的规律,求前i个数的和就从i一次跳lowbit()个就好了
return tmp;
}
void add(int i,int x){//把i以后的部分都加上x(树状数组维护的是前缀和,一个元素改变影响的是它后面的元素)
for(; i <= n; i += lowbit(i)) c[i] += x;
}
区间加：维护原数组的差分数组的前缀和，等价于维护原数组，在一个点+x等价于把后面的数都+x，那么在区间加的区间后面把x减回来就好了
区间求和：区间[l,r]的和等于区间[1,r]的和减去区间[1,l-1]的和
线段树
用分治的思想维护区间，每个结点的左右子结点分别维护该结点所维护的信息的一半
lazy tag：进行区间操作的时候lazy一点，如果当前结点维护的数据不能直接用来操作（比如不完全包含在操作区间内），那么就不直接应用更改，而是只将更改应用于能直接操作的子辈中，当然，那些不能直接操作的子辈也不会应用更改，知道它在之后的操作中可以被直接操作(即每个不能操作的结点都用pushdown把tag分给左右子结点)。当然，在子节点的操作完成后，更改并没有被应用到它的任何一个前辈，因此还需要pushup来将更改逐级上传到当前结点
重点：想清楚要维护的数据如何应用到区间上，tag应该如何传递，大范围的信息怎么由小范围的信息合成，不同tag直接有没有运算优先级关系(比如：区间乘法，维护区间和的方式是把被乘的区间区间和乘以乘数，传递标记的方式是乘法结合律，如果乘的时候有加法tag那么要把加法tag一起乘)
namespace seg{
#define ls tree[root << 1]
#define rs tree[root << 1 | 1]
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
struct node{
int sum;
int add;
int mul;
}tree[maxn * 4];
void pushup(int root){
tree[root].sum = (ls.sum + rs.sum) % p;
}
void pushdown(int root,int l,int r,int mid){
if(!tree[root].add && tree[root].mul == 1) return;
ls.mul *= tree[root].mul,ls.mul %= p;
ls.add *= tree[root].mul,ls.add %= p;
ls.sum *= tree[root].mul,ls.sum %= p;
rs.mul *= tree[root].mul,rs.mul %= p;
rs.add *= tree[root].mul,rs.add %= p;
rs.sum *= tree[root].mul,rs.sum %= p;
ls.add += tree[root].add,ls.add %= p;
rs.add += tree[root].add,rs.add %= p;
ls.sum += tree[root].add * (mid - l + 1),ls.sum %= p;
rs.sum += tree[root].add * (r - mid),rs.sum %= p;
tree[root].add = 0;
tree[root].mul = 1;
}
void build(int root,int l,int r){
tree[root].mul = 1;
tree[root].add = 0;
if(l == r){
tree[root].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
pushup(root);
}
void add(int root,int l,int r,int ql,int qr,int v){
if(ql <= l && r <= qr){
tree[root].sum += (r - l + 1) * v,tree[root].sum %= p;
tree[root].add += v,tree[root].add %= p;;
return;
}
int mid = (l + r) >> 1;
pushdown(root,l,r,mid);
if(ql <= mid) add(lson,ql,qr,v);
if(qr > mid) add(rson,ql,qr,v);
pushup(root);
}
void mul(int root,int l,int r,int ql,int qr,int v){
if(ql <= l && r <= qr){
tree[root].sum *= v,tree[root].sum %= p;
tree[root].add *= v,tree[root].add %= p;
tree[root].mul *= v,tree[root].mul %= p;
return;
}
int mid = (l + r) >> 1;
pushdown(root,l,r,mid);
if(ql <= mid) mul(lson,ql,qr,v);
if(qr > mid) mul(rson,ql,qr,v);
pushup(root);
}
int query(int root,int l,int r,int ql,int qr){
if(ql <= l && r <= qr) return tree[root].sum % p;
int mid = (l + r) >> 1;
int ans = 0;
pushdown(root,l,r,mid);
if(ql <= mid) ans += query(lson,ql,qr),ans %= p;
if(qr > mid) ans += query(rson,ql,qr),ans %= p;
return ans;
}
#undef ls
#undef rs
#undef lson
#undef rson
}