提高组常见模板总结

注$^1$：本文中带有 ~~小粉兔~~ 字样的文字均指不怎么重要的东西。~~主要是不会~~

注$^2$：马蜂良好，可以超，没问题的

## ~~【小粉兔】~~区间数据结构

### 1.ST 表

适用范围：有函数 $f$ 使得 $x = f(x,x)$， 如 $\max,\gcd$ 等 。

代码实现：

```cpp
void init(){
for(int i = 0; i < n; i++)st[i][0] = a[i];
for(int j = 1; j <= Log[n]; j++)
for(int i = 0; i + (1 << j) <= n; i++)
st[i][j] = f(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r){
int s = Log[r - l + 1];
return f(st[l][s], st[r + 1 - (1 << s)][s]);
}
```

时间复杂度：

```query: ``` $O(1)$ ，
```init: ``` $O(n \log n)$ 。

### 2. 线段树

去你小粉兔的。分块万岁。但是 $O(\log n)$ 的查询/修改复杂度~~真的超酷的诶~~

就是用线段树的时候常数大并不是你的人品问题。

总体思想是讲区间变成一颗二叉树从根到叶子处理。

```cpp
struct node{
int l, r, v, lazy;
node(int a, int b, int c, int d){
l = a, r = b, v = c, lazy = d;
}
}tree[maxn * 8];
void build(int p, int l, int r){
int mid = (l + r) >> 1, pl = p << 1, pr = p << 1 | 1;
tree[p] = node(l, r, 0, 0);
if(l == r){
tree[p] = a[l];
return;
}
build(pl, l, mid), build(pr, mid + 1, r);
tree[p].v = f(tree[pl].v, tree[pr].v);
}
void pushdown(int p){
int v = tree[p].lazy, pl = p << 1, pr = p << 1 | 1;
tree[p].lazy = 0;
tree[pl].v = f(tree[pl].v, v), tree[pl].lazy = f(tree[pl].lazy, v);
tree[pr].v = f(tree[pr].v, v), tree[pr].lazy = f(tree[pr].lazy, v);
}
void modify(int p, int l, int r, int w){
int mid, pl = p << 1, pr = p << 1 | 1;
if(tree[p].lazy)pushdown(p);
if(l <= tree[p].l && r <= tree[p].r){
tree[p].lazy = f(tree[p].lazy, w);
tree[p].v = f(tree[p].v, w);
return;
}
mid = (tree[p].l + tree[p].r) >> 1;
if(l <= mid && r >= tree[pl].l)modify(l, r, pl, w);
if(l <= tree[pr].r && r > mid)modify(l, r, pr, w);
tree[p].v = f(tree[pl].v, tree[pr].v);
}
int query(int l, int r, int p){
int lres, rres, mid, pl = p << 1, pr = p << 1 | 1;
if(tree[p].lazy)pushdown(p);
if(l <= tree[p].l && tree[p].r <= r)return tree[p].v;

mid = (l + r) >> 1;
if(l <= mid && tree[pl].l <= r)lres = query(l, r, pl);
if(l <= tree[pl].r && mid < r)rres = query(l, r, pr);
return f(lres, rres);
}
```

### 3. 树状数组

> 他能干的线段树也能干，他不能干的线段树还是能干，所以打分块。

### ~~4.分块（划掉）~~不考

### 5. ~~平衡树~~下辈子学

## 图论

### 1. 链式前向星

~~时间复杂度：等会这他妈有什么复杂度啊啊啊~~

```cpp
struct edge{
int u, v, w, next;
edge(int a, int b, int c, int d){
u = a, v = b, w = c, next = d;
}
}e[maxn];
int elast[maxn];
void add(int u, int v, int w){
e[idx] = edge(u, v, w, elast[x]), elast[x] = ++idx;
}
```

### 2. dijkstra

去你小粉兔的 ${SPFA}$ 。求单源最短路。时间复杂度 $O(n\log n)$ 。

```cpp
struct node{
int u, dis;
friend bool operator < (node a, node b){
return a.dis < b.dis;
}
node(int a, int b){
u = a, dis = b;
}
}
void dijkstra(int p){
priority_queue <node> q;
dis[p] = 0, q.push(p, 0);
while(!q.empty()){
int u = q.top().u;
q.pop();
if(u == b)return;
if(mk[u])continue;
mk[u] = 1;
for(int j = elast[u]; j; j = e[j].next){
int v = e[j].y;
if(dis[v] > dis[u] + e[u].w){
dis[v] = dis[u] + e[u].w;
q.push(node(v, dis[v]));
}
}
}
}
```

### 3. 二分图最大匹配

虽然但是应该不考吧……

```cpp
int dfn = 0, ans;
int cnt[maxn];
bool find(int u){
for(int i = elast[u]; i; i = e[i].next){
if(cnt[i] >= dfn)continue;
cnt[i] = dfn;
if(!elink[i] || find(elink[i])){
elink[i] = u;
return 1;
}
}
return 0;
}
int main(){
for(int i = 1; i <= max(n, m); i++)
dfn++, ans += find(i);
}
```

### 4. Tarjan 求强联通分量，割点，割边

~~估计也不会考，毕竟没考过~~

### 5. 最小生成树 Kruskal

~~看上去简单一些~~

```cpp
bool operator < (edge a, edge b){
return a.w < b.w;
}
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int kruskal(){
int res = 0, cnt = 0;
for(int i = 1; i <= m; i++)fa[i] = i;
sort(e, e + m + 1);
for(int i = 0; i < m; i++){
int u = e[i].u, v = e[i].v, w = e[i].w;
a = find(a), b = find(b);
if(a != b)fa[a] = b, res += w, cnt++;
if(cnt == m - 1)return res;
}
if(cnt == m - 1)return res;
return -1;
}
```