模板 - 普及/提高−难度模板

普及/提高−

B3611 【模板】传递闭包

判断一个点是否能到达另一个点。

因为 $n\leq100$，故用 Floyed 直接是否计算路径。

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
const int inf = 2147483647;

int n;
int dis[N][N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			scanf("%d", &dis[i][j]);
			if (!dis[i][j]) {
				dis[i][j] = inf;
			}
		}
	}

	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (dis[i][k] != inf && dis[k][j] != inf) {
					dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
				}
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (dis[i][j] != inf) {
				printf("1 ");
			} else {
				printf("0 ");
			}
		}
		printf("\n");
	}
	return 0;
}

P3371 【模板】单源最短路径（弱化版）（SPFA）

给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int M = 5e5 + 5;

int n, m, s;
int tot, head[M], dis[N];
bool vis[N];

struct Node {
	int from, to, val;
} edge[M];

void addedge(int u, int v, int w) {
	edge[++tot] = (Node) {
		v, head[u], w
	};
	head[u] = tot;
}

queue <int> q;

void SPFA(int k) {
	q.push(k);
	dis[k] = 0, vis[k] = 1;
	while (!q.empty()) {
		k = q.front();
		q.pop();
		vis[k] = 0;
		for (int i = head[k]; i; i = edge[i].to) {
			int v = edge[i].from, w = edge[i].val;
			if (dis[v] > dis[k] + w) {
				dis[v] = dis[k] + w;
				if (!vis[v]) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return;
}
int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; ++i) {
		dis[i] = 2147483647;
	}
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		addedge(u, v, w);
	}
	SPFA(s);
	for (int i = 1; i <= n; ++i) {
		printf("%d ", dis[i]);
	}
	return 0;
}

P4779 【模板】单源最短路径（标准版）（dijkstra堆优化）

给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int M = 5e5 + 5;

int n, m, s;
int tot, head[M], dis[N];
bool vis[N];

struct Node {
	int from, to, val;
} edge[M];

void addedge(int u, int v, int w) {
	edge[++tot] = (Node) {
		v, head[u], w
	};
	head[u] = tot;
}

priority_queue<pair<int, int>>q;

void dijkstra(int k) {
	q.emplace(make_pair(0, k));
	dis[k] = 0;
	while (!q.empty()) {
		k = q.top().second;
		q.pop();
		if (vis[k]) {
			continue;
		}
		vis[k] = 1;
		for (int i = head[k]; i; i = edge[i].to) {
			int v = edge[i].from, w = edge[i].val;
			if (dis[v] > dis[k] + w) {
				dis[v] = dis[k] + w;
				if (!vis[v]) {
					q.emplace(make_pair(-dis[v], v));
				}
			}
		}
	}
	return;
}

int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; ++i) {
		dis[i] = 2147483647;
	}
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		addedge(u, v, w);
	}
	dijkstra(s);
	for (int i = 1; i <= n; ++i) {
		printf("%d ", dis[i]);
	}
	return 0;
}

P3385 【模板】负环

给定一个 $n$ 个点的有向图，求出图中是否存在从顶点 $1$ 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5;

int T;
int n, m;
int tot, head[N * N];
int dis[N], cnt[N], vis[N];

struct Node {
	int from, to, val;
} edge[N * N];

void addedge(int u, int v, int w) {
	edge[++tot] = (Node) {
		v, head[u], w
	};
	head[u] = tot;
}

queue<int> q;

void SPFA(int k) {
	q.push(k);
	dis[k] = 0, vis[k] = 1;
	while (!q.empty()) {
		k = q.front();
		q.pop();
		vis[k] = 0;
		for (int i = head[k]; i; i = edge[i].to) {
			int v = edge[i].from, w = edge[i].val;
			if (dis[v] > dis[k] + w) {
				dis[v] = dis[k] + w;
				cnt[v] = cnt[k] + 1;
				if (cnt[v] >= n) {
					printf("YES\n");
					return;
					return ;
				}
				if (!vis[v]) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	printf("NO\n");
	return;
}

int main() {
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		while (!q.empty()) {
			q.pop();
		}

		scanf("%d%d", &n, &m);
		for (int j = 1; j <= m; ++j) {
			edge[j].from = 0, edge[j].to = 0;
			head[j] = 0;
		}
		for (int j = 1; j <= n; ++j) {
			dis[j] = 2147483647;
			cnt[j] = 0;
			vis[j] = 0;
		}

		for (int j = 1; j <= m; ++j) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			if (c >= 0) {
				addedge(a, b, c);
				addedge(b, a, c);
			} else {
				addedge(a, b, c);
			}
		}
		SPFA(1);
	}
	return 0;
}

P3374 【模板】树状数组1（单点修改，区间查询）

操作 $1$
格式：1 x k
含义：将第 $x$ 个数加上 $k$
操作 $2$：
格式：2 x y
含义：输出区间 $[x,y]$ 内每个数的和

树状数组做法

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m;
int tree[N];

int lowbit(int x) {
	return x & (-x);
}

void add(int i, int x) {
	while (i <= n) {
		tree[i] += x;
		i += lowbit(i);
	}
	return;
}

int sum(int x) {
	int ans = 0;
	while (x) {
		ans += tree[x];
		x -= lowbit(x);
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		int a;
		scanf("%d", &a);
		add(i, a);
	}
	
	for (int i = 1; i <= m; ++i) {
		int op, a, b;
		scanf("%d%d%d", &op, &a, &b);
		if (op == 1) {
			add(a, b);
		}
		if (op == 2) {
			printf("%d\n", sum(b) - sum(a - 1));
		}
	}
	return 0;
}

线段树做法

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m;
int a[N];

struct Node {
	int l, r;
	int sum;
} tree[N * 4];

void build(int i, int l, int r) {
	tree[i].l = l, tree[i].r = r;
	if (l == r) {
		tree[i].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid);
	build(i << 1 | 1, mid + 1, r);
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
	return;
}

int query(int i, int l, int r) {
	if (l <= tree[i].l && r >= tree[i].r) {
		return tree[i].sum;
	}
	int s = 0;
	int mid = (tree[i].l + tree[i].r) >> 1;
	if (l <= mid) {
		s += query(i << 1, l, r);
	}
	if (r > mid) {
		s += query(i << 1 | 1, l, r);
	}
	return s;
}

void add(int i, int add_i, int add_sum) {
	if (tree[i].l == tree[i].r) {
		tree[i].sum += add_sum;
		return;
	}
	int mid = (tree[i].l + tree[i].r) >> 1;
	if (add_i <= mid) {
		add(i << 1, add_i, add_sum);
	} else {
		add(i << 1 | 1, add_i, add_sum);
	}
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
	return;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	build(1, 1, n);
	for (int i = 1; i <= m; ++i) {
		int op, a, b;
		scanf("%d%d%d", &op, &a, &b);
		if (op == 1) {
			add(1, a, b);
		} else {
			printf("%d\n", query(1, a, b));
		}
	}
	return 0;
}

P3368 【模板】树状数组2（区间修改，单点查询）

操作 $1$
格式：1 x y k
含义：将区间 $[x,y]$ 内每个数加上 $k$
操作 $2$：
格式：2 x
含义：输出第 $x$ 个数的值

树状数组做法

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m;
int a[N], tree[N];

int lowbit(int x) {
	return x & -x;
}

void add(int i, int x) {
	while (i <= n) {
		tree[i] += x;
		i += lowbit(i);
	}
	return ;
}

int sum(int x) {
	int ans = 0;
	while (x) {
		ans += tree[x];
		x -= lowbit(x);
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}

	for (int i = 1; i <= m; ++i) {
		int op, x;
		scanf("%d", &op);
		if (op == 1) {
			int y, z;
			scanf("%d%d%d", &x, &y, &z);
			add(x, z);
			add(y + 1, -z);
		} else if (op == 2) {
			scanf("%d", &x);
			printf("%d\n", a[x] + sum(x));
		}
	}
	return 0;
}

线段树做法

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m;
int a[N];

struct Node {
	int l, r;
	int sum, add;
} tree[N * 4];

void pushdown(int i) {
	if (tree[i].add) {
		tree[2 * i].add += tree[i].add;
		tree[2 * i + 1].add += tree[i].add;
		tree[2 * i].sum += tree[i].add * (tree[2 * i].r - tree[2 * i].l + 1);
		tree[2 * i + 1].sum += tree[i].add * (tree[2 * i + 1].r - tree[2 * i + 1].l + 1);
		tree[i].add = 0;
	}
}

void build(int i, int l, int r) {
	tree[i].l = l, tree[i].r = r;
	if (l == r) {
		tree[i].sum = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(i << 1, l, mid);
	build(i << 1 | 1, mid + 1, r);
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
	return;
}

void update_add(int i, int add_l, int add_r, int add_sum) {
	if (tree[i].l >= add_l && tree[i].r <= add_r) {
		tree[i].sum += add_sum * (tree[i].r - tree[i].l + 1);
		tree[i].add += add_sum;
		return ;
	}
	pushdown(i);
	int mid = (tree[i].l + tree[i].r) / 2;
	if (add_l <= mid) {
		update_add(i << 1, add_l, add_r, add_sum);
	}
	if (add_r > mid) {
		update_add(i << 1 | 1, add_l, add_r, add_sum);
	}
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
	return;
}

int query(int i, int query_i) {
	if (tree[i].l == tree[i].r) {
		return tree[i].sum;
	}
	pushdown(i);
	int mid = (tree[i].l + tree[i].r) / 2;
	if (query_i <= mid) {
		return query(i << 1, query_i);
	} else {
		return query(i << 1 | 1, query_i);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	build(1, 1, n);
	for (int i = 1; i <= m; ++i) {
		int op, a;
		scanf("%d", &op);
		if (op == 1) {
			int b, c;
			scanf("%d%d%d", &a, &b, &c);
			update_add(1, a, b, c);
		} else {
			scanf("%d", &a);
			cout << query(1, a)  << endl;
		}
	}
	return 0;
}

P3366 【模板】最小生成树

$kruskal$ 算法

#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 5;
const int M = 2e5 + 5;

int n, m;
int fa[N];
int ltt, ans;

struct node {
	int from, to, val;
} edge[M];

bool cmp(node x, node y) {
	return x.val < y.val;
}

int find(int x) {
	if (fa[x] == x) {
		return x;
	}
	return fa[x] = find(fa[x]);
}

void kruskal() {
	sort(edge, edge + m, cmp);
	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	for (int i = 1; i <= m; ++i) {
		int u = edge[i].from, v = edge[i].to;
		u = find(u), v = find(v);
		if (u != v) {
			++ltt;
			ans += edge[i].val;
			fa[u] = v;
		}
	}
	if (ltt < n - 1) {
		printf("orz");
	} else {
		printf("%d", ans);
	}
	return;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].val);
	}
	kruskal();
	return 0;
}

$Prim$ 算法

#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 5;
const int inf = 2147483647;

int n, m, ans;
int g[5001][5001], vis[5005], dis[5005];
int minn = inf, k, v[5005];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; j++) {
			g[i][j] = inf;
		}
	}
	for (int i = 1; i <= m; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if (g[x][y] != inf) {
			g[x][y] = min(z, g[x][y]);
			g[y][x] = min(z, g[y][x]);
			v[x] = v[y] = 1;
		} else if (x == y) {
			g[x][y] = 0;
		} else {
			g[x][y] = z;
			g[y][x] = z;
			v[x] = v[y] = 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (!v[i]) {
			printf("orz");
			return 0;
		}
	}
	for (int i = 1; i <= n; ++i) {
		dis[i] = inf;
	}
	dis[1] = 0;
	for (int i = 1; i <= n; ++i) {
		minn = inf;
		k = -1;
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && minn > dis[j]) {
				minn = dis[j];
				k = j;
			}
		}
		if (k == -1) {
			printf("orz");
			return 0;
		}
		vis[k] = 1;
		ans += dis[k];
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && dis[j] > g[k][j]) {
				dis[j] = g[k][j];
			}
		}
	}
	printf("%d", ans);
	return 0;
}

P3379 【模板】最近公共祖先

倍增

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m, s;
int tot, head[N];
int dep[N], f[N][21];

struct tree {
	int from, to;
} edge[2 * N];

void addedge(int u, int v) {
	edge[++tot] = (tree) {
		v, head[u]
	};
	head[u] = tot;
}

void dfs(int son, int father) {
	dep[son] = dep[father] + 1;
	f[son][0] = father;
	for (int i = 1; i <= 20; ++i) {
		f[son][i] = f[f[son][i - 1]][i - 1];
	}
	for (int i = head[son]; i; i = edge[i].to) {
		int v = edge[i].from;
		if (v == father) {
			continue;
		}
		dfs(v, son);
	}
	return;
}

int lca(int a, int b) {
	if (dep[a] < dep[b]) {
		swap(a, b);
	}
	for (int i = 20; i >= 0; --i) {
		if (dep[f[a][i]] >= dep[b]) {
			a = f[a][i];
		}
	}
	if (a == b) {
		return a;
	}
	for (int i = 20; i >= 0; --i) {
		if (f[a][i] != f[b][i]) {
			a = f[a][i];
			b = f[b][i];
		}
	}
	return f[a][0];
}

int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		addedge(u, v), addedge(v, u);
	}
	dep[s] = 1;
	lca(s, 0);
	for (int i = 1; i <= m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", lca(a, b));
	}
	return 0;
}

$tarjan$

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m, s;
int tot, head[N];
int vis[N], fa[N], ans[N];
vector<pair<int, int>> ask[N];

struct tree {
	int from, to;
} edge[2 * N];

void addedge(int u, int v) {
	edge[++tot] = (tree) {
		v, head[u]
	};
	head[u] = tot;
}

int find(int x) {
	if (fa[x] == x) {
		return x;
	}
	return fa[x] = find(fa[x]);
}

void tarjan(int u) {
	vis[u] = 1;
	for (int i = head[u]; i; i = edge[i].to) {
		int v = edge[i].from;
		if (!vis[v]) {
			tarjan(v);
			fa[v] = u;
		}
	}
	for (auto q : ask[u]) {
		if (vis[q.first]) {
			ans[q.second] = find(q.first);
		}
	}
	return;
}

int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		addedge(u, v), addedge(v, u);
	}
	for (int i = 1; i <= m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		ask[a].push_back({b, i});
		ask[b].push_back({a, i});
	}

	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	tarjan(s);

	for (int i = 1; i <= m; ++i) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

树链剖分

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m, s;
int head[N], tot;
int dep[N], fa[N];
int zs_sz[N], zhong_son[N];
int top[N];

struct Node {
	int from, to;
} edge[2 * N];

void addedge(int u, int v) {
	edge[++tot] = (Node) {
		v, head[u]
	};
	head[u] = tot;
	return;
}

void dfs1(int son, int father) {
	fa[son] = father;
	dep[son] = dep[father] + 1;
	zs_sz[son] = 1;
	for (int i = head[son]; i; i = edge[i].to) {
		int v = edge[i].from;
		if (v == father) {
			continue;
		}
		dfs1(v, son);
		zs_sz[son] += zs_sz[v];
		if (zs_sz[zhong_son[son]] < zs_sz[v]) {
			zhong_son[son] = v;
		}
	}
	return;
}

void dfs2(int son, int t) {
	top[son] = t;
	if (!zhong_son[son]) {
		return;
	}
	dfs2(zhong_son[son], t);
	for (int i = head[son]; i; i = edge[i].to) {
		int v = edge[i].from;
		if (v == fa[son] || v == zhong_son[son]) {
			continue;
		}
		dfs2(v, v);
	}
	return;
}

int lca(int a, int b) {
	while (top[a] != top[b]) {
		if (dep[top[a]] < dep[top[b]]) {
			swap(a, b);
		}
		a = fa[top[a]];
	}
	return ((dep[a] < dep[b]) ? a : b);
}

int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		addedge(u, v);
		addedge(v, u);
	}
	dfs1(s, 0), dfs2(s, s);
	for (int i = 1; i <= m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", lca(a, b));
	}
	return 0;
}

P8306 【模板】字典树

#include<bits/stdc++.h>
using namespace std;

const int N = 3e6 + 5;

int T;
int n, q;
int trie[N][150];
int tot, cnt[N];

void insert(string s) {
	int p = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (!trie[p][s[i]]) {
			trie[p][s[i]] = ++tot;
		}
		p = trie[p][s[i]];
		++cnt[p];
	}
	return;
}

int find(string s) {
	int p = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (!trie[p][s[i]]) {
			return 0;
		}
		p = trie[p][s[i]];
	}
	return cnt[p];
}

int main() {
	scanf("%d", &T);
	for (int ask = 1; ask <= T; ++ask) {
		for (int i = 0; i <= tot; ++i) {
			for (int j = 0; j < 150; ++j) {
				trie[i][j] = 0;
			}
		}
		for (int i = 0; i <= tot; ++i) {
			cnt[i] = 0;
		}
		tot = 0;
		scanf("%d%d", &n, &q);
		for (int i = 1; i <= n; ++i) {
			string s;
			cin >> s;
			insert(s);
		}
		for (int i = 1; i <= q; ++i) {
			string s;
			cin >> s;
			printf("%d\n", find(s));
		}
	}
	return 0;
}

P1883 【模板】三分

给定 $n$ 个二次函数 $f_1(x),f_2(x),\dots,f_n(x)$（均形如 $ax^2+bx+c$），设 $F(x)=\max{f_1(x),f_2(x),…,f_n(x)}$，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;

int T;
int n;
int a[N], b[N], c[N];

double f(double m) {
	double ans = -1e9;
	for (int i = 1; i <= n; ++i) {
		ans = max(ans, a[i] * m * m + b[i] * m + c[i]);
	}
	return ans;
}

int main() {
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		scanf("%d", &n);
		for (int j = 1; j <= n; ++j) {
			scanf("%d%d%d", &a[j], &b[j], &c[j]);
		}
		double l = 0, r = 1000;
		while (fabs(r - l) > 1e-9) {
			double mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
			if (f(mid1) > f(mid2)) {
				l = mid1;
			} else {
				r = mid2;
			}
		}
		printf("%.4lf\n", f(l));
	}
	return 0;
}

P1886 【模板】单调队列 / 滑动窗口

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 $[1,3,-1,-3,5,3,6,7]$ 以及 $k = 3$，有如下过程：

$$
\def\arraystretch{1.2}
\begin{array}{|c|c|c|}\hline
\textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \ \hline
\verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \ \hline
\verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \ \hline
\verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \ \hline
\verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \ \hline
\verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \ \hline
\verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \ \hline
\end{array}
$$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int n, m;
int a[N];
int ans[N];
deque<int> q;

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}

//	最大值
	for (int i = 1; i <= n; ++i) {
		while (!q.empty() && a[i] <= a[q.back()]) {
			q.pop_back();
		}
		q.push_back(i);
		if (m < q.back() - q.front() + 1) {
			q.pop_front();
		}
		ans[i] = a[q.front()];
	}
	for (int i = m; i <= n; i++) {
		printf("%d ", ans[i]);
	}
	printf("\n");


// 	最大值
	while (!q.empty()) {
		q.pop_front();
	}
	for (int i = 1; i <= n; ++i) {
		while (!q.empty() && a[i] >= a[q.back()]) {
			q.pop_back();
		}
		q.push_back(i);
		if (m < q.back() - q.front() + 1) {
			q.pop_front();
		}
		ans[i] = a[q.front()];
	}

	for (int i = m; i <= n; ++i) {
		printf("%d ", ans[i]);
	}
	return 0;
}

P5788 【模板】单调栈

定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标，即 $f(i)=\min_{i<j\leq n, a_j > a_i} {j}$。若不存在，则 $f(i)=0$，求出 $f(1\dots n)$。

#include<bits/stdc++.h>
using namespace std;

const int N = 3e6 + 5;

int n;
int a[N];
int ans[N];
stack<int> s;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}

	for (int i = n; i >= 1; --i) {
		while (!s.empty() && a[s.top()] <= a[i]) {
			s.pop();
		}
		if (s.empty()) {
			ans[i] = 0;
		} else {
			ans[i] = s.top();
		}
		s.push(i);
	}
	
	for (int i = 1; i <= n; ++i) {
		printf("%d ", ans[i]);
	}
	return 0;
}

P3367 【模板】并查集

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;

int n, m;
int fa[N];

int find(int x) {
	if (fa[x] == x) {
		return x;
	}
	return fa[x] = find(fa[x]);
}

void unionn(int x, int y) {
	fa[find(x)] = find(y);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	for (int i = 1; i <= m; ++i) {
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
			unionn(x, y);
		} else {
			printf((find(x) == find(y)) ? "Y\n" : "N\n");
		}
	}
	return 0;
}
````

<div STYLE="page-break-after: always;"></div>

### <span style='color:black;font-family:华文楷体;'>P3865 【模板】ST 表 && RMQ 问题</span>
静态区间最大值问题，每次询问返回区间内数字的最大值。

$f[i][j]$：指的是在序列的第 $i$ 项，向后 $2^j$ 个元素所包含序列间的最大值。

定理：
$$
log\ i=log\ \frac{i}{2}+1
$$

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, m;
int lg[N];
int f[N][25];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 2; i <= n; ++i) {
		lg[i] = lg[i / 2] + 1;
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &f[i][0]);
	}
	for (int i = 1; i <= lg[n]; ++i) {
		for (int j = 1; j <= n - pow(2, i) + 1; ++j) {
			f[j][i] = max(f[j][i - 1], f[j + int(pow(2, i - 1))][i - 1]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		int l, r;
		scanf("%d%d", &l, &r);
		int k = lg[r - l + 1];
		printf("%d\n", max(f[l][k], f[r - int(pow(2, k)) + 1][k]));
	}
	return 0;
}

P3811 【模板】模意义下的乘法逆元

给定 $n,p$，求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。

这里 $a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。

#include<bits/stdc++.h>
using namespace std;

int n, p;
int x, y;

void exgcd(int a, int b) {
	if (!b) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a % b);
	int tp = x;
	x = y;
	y = tp - a / b * y;
	return;
}

int main() {
	scanf("%d%d", &n, &p);
	for (int i = 1; i <= n; ++i) {
		exgcd(i, p);
		printf("%d\n", (x % p + p) % p);
	}
	return 0;
}

P4549 【模板】裴蜀定理

对于任意整数 $a,b,d$，$gcd(a,b)|d \Leftrightarrow \exists \ u,v： ua+vb = d$

证明可以通过递归构造解来证明：

首先显然当 $u=1,v=0$ 的时候显然成立。假设存在 $u’,v’$，使得 $u’b+v’(a\ mod\ b)=d$.

注意到 $$a\ mod\ b = a-\lfloor\frac{a}{b}\rfloor b$$，可得 $$ u’b + v’(a-\lfloor\frac{a}{b}\rfloor b) = d$$

整理可以得到：

$$u’b + v’a- v’\lfloor\frac{a}{b}\rfloor b = d$$

$$v’a + (u’-\lfloor\frac{a}{b}\rfloor v’)b = d$$

归纳证明该定理正确。

扩展到求 $ax+by=c$ 的最小非负 $c$，显然 $c$ 要满足 $gcd(a,b)|c$，所以 $c$ 取 $gcd(a,b)$ 是最小的。

扩展到这个题目，如果有多个数字的话，考虑前两个数字 $a_1,a_2$,有 $a_1x+a_2y=S \Rightarrow gcd(a_1,a_2)|d，$$gcd(a_1,a_2) =d$，所以把这两个的答案合并直接去取下一个就可以了。

#include<bits/stdc++.h>
using namespace std;

int n;
int ans;

int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int a;
		scanf("%d", &a);
		a = abs(a);
		ans = gcd(ans, a);
	}
	printf("%d", ans);
	return 0;
}

模板

模板 - 普及-难度模板下一篇