前言本文主要包含算法竞赛一些常用的板子，码风可能不是太好，还请见谅 。
后续会继续补充没有的板子 。当然我太菜了有些可能写不出来T^T
稍微有些分类但不多，原谅我QwQ
建议 Ctrl + F 以快速查找板子 。
常用板子树状数组此处为查询区间和的树状数组 。
int bit[500010];void add(int k, int x) { while (k <= n) {bit[k] += x;k += lowbit(k); }}int ask(int k) { int res = 0; while (k) {res += bit[k];k -= lowbit(k); } return res;}线段树此处为区间修改区间查询区间和的线段树 。
struct SegmentTree { ll sum[N << 2], lazy[N << 2]; int l[N << 2], r[N << 2]; void update(int rt) {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void pushdown(int rt) {if (!lazy[rt]) return ;sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt], lazy[rt << 1] += lazy[rt];sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt], lazy[rt << 1 | 1] += lazy[rt];lazy[rt] = 0;update(rt); } void build(int rt, int L, int R) {l[rt] = L, r[rt] = R;if (L == R) {sum[rt] = a[L];return ;}int mid = L + R >> 1;build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R);update(rt); } void change(int rt, int L, int R, int x) {if (L <= l[rt] && r[rt] <= R) {sum[rt] += (r[rt] - l[rt] + 1) * x;lazy[rt] += x;return ;}pushdown(rt);if (L <= r[rt << 1]) change(rt << 1, L, R, x);if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x);update(rt); } ll query(int rt, int L, int R) {if (L <= l[rt] && r[rt] <= R) return sum[rt];pushdown(rt);ll res = 0;if (L <= r[rt << 1]) res += query(rt << 1, L, R);if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R);return res; }} tree;堆不是吧真有人手写堆吗
ll q[N], cnt;void pushup(int id) { while (id > 1) {if (q[id] >= q[id >> 1]) break;swap(q[id], q[id >> 1]);id >>= 1; }}void movedown() { int id = 1; while (id << 1 <= cnt) {if ((id << 1 | 1) <= cnt) {if (q[id] < min(q[id << 1], q[id << 1 | 1])) break;;if (q[id << 1] < q[id << 1 | 1]) swap(q[id], q[id << 1]), id <<= 1;else swap(q[id], q[id << 1 | 1]), id = id << 1 | 1;}else {if (q[id] > q[id << 1]) swap(q[id], q[id << 1]);break;} }}void add(ll x) { q[++cnt] = x; pushup(cnt);}void pop() { swap(q[1], q[cnt]); cnt--; movedown();}并查集struct Disjoint_Set { int p[N], size[N]; void build() {for (int i = 1; i <= n; i++) p[i] = i, size[i] = 1; } int root(int x) {if (p[x] != x) return p[x] = root(p[x]);return x; } void merge(int x, int y) {x = root(x), y = root(y);if (size[x] > size[y]) swap(x, y);p[x] = y;size[y] += size[x]; } bool check(int x, int y) {x = root(x), y = root(y);return x == y; }} a;ST表代码实现查询区间 \([l, r]\) 的区间最大值
for (int i = 1; i <= n; i++) st[0][i] = a[i];for (int j = 1; j <= lg; j++) { for (int i = 1; i <= n - (1 << j) + 1; i++) {st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]); }}int l, r, lg2, len;for (int i = 1; i <= m; i++) { l = read(), r = read(); lg2 = log2(r - l + 1); len = 1 << lg2; printf("%d\n", max(st[lg2][l], st[lg2][r - len + 1]));}边链表const int N = 100010;int last[N], cnt;struct edge { int to, next, w;} e[N << 1];void addedge(int x, int y, int w) { e[++cnt].to = y; e[cnt].next = last[x]; e[cnt].w = w; last[x] = cnt;}LCA此处贴的是 Tarjan法 求LCA 。更多方法
struct Disjoint_Set { int p[N], size[N]; void build() {for (int i = 1; i <= n; i++) p[i] = i, size[i] = 1; } int root(int x) {if (p[x] != x) return p[x] = root(p[x]);return x; } void merge(int x, int y) {x = root(x), y = root(y);if (size[x] > size[y]) swap(x, y);p[x] = y;size[y] += size[x]; } bool check(int x, int y) {x = root(x), y = root(y);return x == y; }} a;int last[N], cnt;struct edge { int to, next;} e[N << 1];void addedge(int x, int y) { e[++cnt].to = y; e[cnt].next = last[x]; last[x] = cnt;}struct node { int x, y, ans;} ask[N];vector <int> g[N];int p[N];bool vis[N];int r[N];void dfs(int x, int f) { p[x] = f; for (int i = last[x]; i; i = e[i].next) {int v = e[i].to;if (v == f) continue;vis[v] = 1;for (int j : g[v]) {int o = ask[j].x;if (o == v) o = ask[j].y;if (!vis[o]) continue;ask[j].ans = r[a.root(o)];}dfs(v, x);a.merge(x, v);r[a.root(x)] = x; }}单源最短路（Dijkstra）这里是堆优化版呢 。笑了有些时候堆优化还没不优化好
void dij(int s) { priority_queue <pii, vector<pii>, greater<pii> > q; memset(dis, 0x7f7f7f7f, sizeof(dis)); q.push({0, s}); dis[s] = 0; while (!q.empty()) {pii u = q.top(); q.pop();int pos = u.second;if (vis[pos]) continue;vis[pos] = 1;for (int j = last[pos]; j; j = e[j].next) {int v = e[j].to;if (vis[v]) continue;if (dis[pos] + e[j].w < dis[v]) dis[v] = dis[pos] + e[j].w, q.push({dis[v], v});} }