UPD 2026.03.17：完善并添加一些板子给自己考CSP用，AI太好用了你们知道吗
UPD 2026.08.17：上300大失败，板子用处有限啊还是好好练大模拟吧，哭哭
数据结构
线段树
// 线段树模板
// 支持：单点修改、区间修改（区间加、区间乘）、区间查询（区间求和、区间最大值、区间GCD）
// 双懒标记语义：对区间内每个元素先乘 lazy_mul、再加 lazy_add
// 注意：区间GCD与区间乘兼容（gcd(ka,kb)=k·gcd(a,b)），但与区间加不兼容
// （因为 gcd(a+d, b+d) ≠ gcd(a,b)+d），请勿在同一题中混用区间加与GCD查询
#include <bits/stdc++.h>
using namespace std;
int n, m; // n：元素个数，m：操作次数，根据题目调整
const int MAXN = 100005; // 根据题目调整
// -----------------------------------------------------------------------
// 线段树节点
// -----------------------------------------------------------------------
struct Node
{
long long sum; // 区间和
long long mx; // 区间最大值
long long gcd; // 区间GCD（与区间乘兼容；与区间加不兼容，混用时结果不保证正确）
long long lazy_mul; // 懒标记：乘法因子，初始为 1
long long lazy_add; // 懒标记：加法增量，初始为 0
// 待传语义：对子区间每个元素先乘 lazy_mul，再加 lazy_add
int len; // 区间长度（建树时写入，后续不变）
} tree[MAXN * 4];
// -----------------------------------------------------------------------
// 内部辅助：向上更新（由两个子节点合并父节点）
// -----------------------------------------------------------------------
void push_up(int node)
{
tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
tree[node].mx = max(tree[node * 2].mx, tree[node * 2 + 1].mx);
tree[node].gcd = __gcd(tree[node * 2].gcd, tree[node * 2 + 1].gcd);
}
// -----------------------------------------------------------------------
// 内部辅助：对节点 node 直接施加"先乘 mul、再加 add"的复合操作（不递归向下）
// -----------------------------------------------------------------------
void apply(int node, long long mul, long long add)
{
tree[node].sum = mul * tree[node].sum + add * tree[node].len;
tree[node].mx = mul * tree[node].mx + add;
tree[node].gcd = mul * tree[node].gcd; // gcd(ka,kb)=k·gcd(a,b)，乘法对GCD兼容
// add 不作用于 gcd，调用方需保证不混用区间加与GCD查询
// 更新懒标记：将新操作 (mul, add) 追加合并到已有 lazy 上
// 设已有 lazy 为 f(x) = lazy_mul·x + lazy_add
// 新操作为 g(x) = mul·x + add
// 合并后 g(f(x)) = mul·(lazy_mul·x + lazy_add) + add = mul·lazy_mul·x + mul·lazy_add + add
tree[node].lazy_mul = mul * tree[node].lazy_mul;
tree[node].lazy_add = mul * tree[node].lazy_add + add;
}
// -----------------------------------------------------------------------
// 内部辅助：将懒标记向下传递给两个子节点并清空
// -----------------------------------------------------------------------
void push_down(int node)
{
long long mul = tree[node].lazy_mul;
long long add = tree[node].lazy_add;
if (mul != 1 || add != 0)
{
apply(node * 2, mul, add);
apply(node * 2 + 1, mul, add);
tree[node].lazy_mul = 1; // 恢复乘法单位元
tree[node].lazy_add = 0; // 恢复加法单位元
}
}
// -----------------------------------------------------------------------
// 建树：从数组 a[1..n] 建立线段树
// node：当前节点编号（根为 1），l / r：当前节点管辖的区间 [l, r]
// -----------------------------------------------------------------------
void build(int node, int l, int r, long long a[])
{
tree[node].lazy_mul = 1;
tree[node].lazy_add = 0;
tree[node].len = r - l + 1;
if (l == r)
{
tree[node].sum = tree[node].mx = tree[node].gcd = a[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid, a);
build(node * 2 + 1, mid + 1, r, a);
push_up(node);
}
// -----------------------------------------------------------------------
// 区间加（区间修改）：将 [ql, qr] 中每个元素加上 val
// 令 ql == qr 即退化为单点修改
// 注意：区间加与GCD查询不兼容，混用时GCD结果不保证正确
// -----------------------------------------------------------------------
void update_add(int node, int l, int r, int ql, int qr, long long val)
{
if (ql <= l && r <= qr)
{
apply(node, 1, val); // mul=1（不缩放），add=val
return;
}
push_down(node);
int mid = (l + r) / 2;
if (ql <= mid) update_add(node * 2, l, mid, ql, qr, val);
if (qr > mid) update_add(node * 2 + 1, mid + 1, r, ql, qr, val);
push_up(node);
}
// -----------------------------------------------------------------------
// 区间乘（区间修改）：将 [ql, qr] 中每个元素乘以 val
// 令 ql == qr 即退化为单点修改
// 区间乘与GCD查询兼容（gcd(ka,kb)=k·gcd(a,b)），可放心同时使用
// -----------------------------------------------------------------------
void update_mul(int node, int l, int r, int ql, int qr, long long val)
{
if (ql <= l && r <= qr)
{
apply(node, val, 0); // mul=val，add=0（不偏移）
return;
}
push_down(node);
int mid = (l + r) / 2;
if (ql <= mid) update_mul(node * 2, l, mid, ql, qr, val);
if (qr > mid) update_mul(node * 2 + 1, mid + 1, r, ql, qr, val);
push_up(node);
}
// -----------------------------------------------------------------------
// 区间查询
// -----------------------------------------------------------------------
// 查询区间和
long long query_sum(int node, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr) return tree[node].sum;
push_down(node);
int mid = (l + r) / 2;
long long res = 0;
if (ql <= mid) res += query_sum(node * 2, l, mid, ql, qr);
if (qr > mid) res += query_sum(node * 2 + 1, mid + 1, r, ql, qr);
return res;
}
// 查询区间最大值
long long query_max(int node, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr) return tree[node].mx;
push_down(node);
int mid = (l + r) / 2;
long long res = LLONG_MIN;
if (ql <= mid) res = max(res, query_max(node * 2, l, mid, ql, qr));
if (qr > mid) res = max(res, query_max(node * 2 + 1, mid + 1, r, ql, qr));
return res;
}
// 查询区间GCD（建议仅在单点修改场景下使用，区间加场景可能不准确）
// gcd(x, 0) = x，故初始值用 0
long long query_gcd(int node, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr) return tree[node].gcd;
push_down(node);
int mid = (l + r) / 2;
long long res = 0;
if (ql <= mid) res = __gcd(res, query_gcd(node * 2, l, mid, ql, qr));
if (qr > mid) res = __gcd(res, query_gcd(node * 2 + 1, mid + 1, r, ql, qr));
return res;
}
// -----------------------------------------------------------------------
// 对外接口（统一从根节点 1，管辖区间 [1, n] 开始调用）
// -----------------------------------------------------------------------
long long a[MAXN]; // 原始数组（1-indexed）
// 建树，使用前必须先填好 a[] 和 n
void seg_build() { build(1, 1, n, a); }
// 区间加：将 [l, r] 每个元素加 val（与GCD查询不兼容）
void seg_add(int l, int r, long long val) { update_add(1, 1, n, l, r, val); }
// 区间乘：将 [l, r] 每个元素乘以 val（与GCD查询兼容）
void seg_mul(int l, int r, long long val) { update_mul(1, 1, n, l, r, val); }
// 单点加：将下标 pos 的元素加 val（区间加的特殊情形）
void seg_point_add(int pos, long long val) { update_add(1, 1, n, pos, pos, val); }
// 单点乘：将下标 pos 的元素乘以 val（区间乘的特殊情形）
void seg_point_mul(int pos, long long val) { update_mul(1, 1, n, pos, pos, val); }
// 区间求和
long long seg_sum(int l, int r) { return query_sum(1, 1, n, l, r); }
// 区间最大值
long long seg_max(int l, int r) { return query_max(1, 1, n, l, r); }
// 区间GCD（仅单点修改场景推荐）
long long seg_gcd(int l, int r) { return query_gcd(1, 1, n, l, r); }
// 单点查询（sum / max / gcd 在单点时等价，此处统一返回 sum）
long long seg_point_query(int pos) { return query_sum(1, 1, n, pos, pos); }
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
seg_build();
// 使用示例（根据题目填写）：
// seg_add(l, r, val); // 区间 [l,r] 每个元素加 val（与GCD查询不兼容）
// seg_mul(l, r, val); // 区间 [l,r] 每个元素乘以 val（与GCD查询兼容）
// seg_point_add(pos, val); // 单点 pos 加 val
// seg_point_mul(pos, val); // 单点 pos 乘以 val
// seg_sum(l, r); // 区间求和
// seg_max(l, r); // 区间最大值
// seg_gcd(l, r); // 区间GCD（仅与区间乘配合使用，不可与区间加混用）
// seg_point_query(pos); // 单点查询
system("pause");
return 0;
}
ST表
// ST 表（Sparse Table）模板
// 适用：区间可重复贡献问题，即操作满足幂等性：op(x, x) = x
// 本模板以维护【区间最大值】为例
//
// 【若要改为维护其他问题，只需修改两处标注了"【合并操作修改处】"的地方】：
// - 区间最小值：将 max 改为 min
// - 区间GCD： 将 max 改为 __gcd
// - 区间按位AND：将 max(a, b) 改为 (a & b)
// - 区间按位OR： 将 max(a, b) 改为 (a | b)
// 注意：区间求和不满足幂等性（sum(x, x) = 2x ≠ x），不适用 ST 表。
//
// 预处理时间：O(n log n)，查询时间：O(1)，空间：O(n log n)
// 不支持修改操作；若需修改，请改用线段树。
#include <bits/stdc++.h>
using namespace std;
int n, m; // n：元素个数，m：查询次数，根据题目调整
const int MAXN = 100005; // 根据题目调整
const int MAXLOG = 17; // 满足 2^MAXLOG >= MAXN，2^17 = 131072 > 100000
long long st[MAXN][MAXLOG]; // st[i][j]：从下标 i 开始、长度为 2^j 的区间的最大值
int lg[MAXN]; // lg[i] = floor(log2(i))，预处理加速查询
// -----------------------------------------------------------------------
// 预处理对数表与 ST 表
// a[1..n]：原始数组（1-indexed）
// -----------------------------------------------------------------------
void build(long long a[])
{
// 预处理对数表（线性递推，避免每次调用 log2）
lg[1] = 0;
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
// 初始化：长度为 1 的区间（2^0 = 1），直接取原始值
for (int i = 1; i <= n; i++)
st[i][0] = a[i];
// 递推：st[i][j] = op(st[i][j-1], st[i + 2^(j-1)][j-1])
// 即将长度 2^j 的区间拆成两段长度 2^(j-1) 的区间合并
// 【合并操作修改处 1/2】：将 max 改为目标操作
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
// -----------------------------------------------------------------------
// 查询区间 [l, r] 的最大值，O(1)
// 取 k = floor(log2(r-l+1))，用两段长为 2^k 的区间覆盖 [l, r]
// 两段允许重叠，因为最大值满足幂等性：max(x, x) = x
// -----------------------------------------------------------------------
long long query(int l, int r)
{
int k = lg[r - l + 1];
// 【合并操作修改处 2/2】：将 max 改为目标操作
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
// -----------------------------------------------------------------------
// 对外接口
// -----------------------------------------------------------------------
long long a[MAXN]; // 原始数组（1-indexed）
// 建表，使用前必须先填好 a[] 和 n
void st_build() { build(a); }
// 查询区间 [l, r] 的最大值
long long st_query(int l, int r) { return query(l, r); }
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
st_build();
// 使用示例（根据题目填写）：
// for (int i = 0; i < m; i++)
// {
// int l, r;
// cin >> l >> r;
// cout << st_query(l, r) << "\n";
// }
system("pause");
return 0;
}
并查集
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
const int M=2*1e5+5;
const ll inf=0x7fffffff; //2147483647
const int mod=1e9+7;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={0,0,-1,0,1};
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0' && ch<='9'){x=(x<<3)+(x<<1);x+=(ch-'0');ch=getchar();}
return x*f;
}
void write(int x)
{
if (x<0) putchar('-'),x=-x;
if (x>10) write(x/10);
putchar(x%10+'0');
}
int n,m,f[N];
int find(int x){return f[x] == x ? x : f[x] = find(f[x]);
}
int main()
{
cin>>n>>m;
for (int i = 1;i <= n;i++)
f[i] = i;
for (int i = 1;i <= m;i++)
{
int z,x,y;
cin>>z>>x>>y;
if (z==1)
f[find(x)]=find(y); //将能找到最早的祖先节点合并
else if (find(x)==find(y))
cout<<"Y\n";
else
cout<<"N\n";
}
return 0;
}
图论
堆优化Dijkstra
#include <bits/stdc++.h>
using namespace std;
int n, m; // 节点数、边数，根据题目调整
// adj[u]：存储从 u 出发的有向边 {终点 v, 权值 w}，用于 Dijkstra
// 注意：权值为 int，若单条边权可能超过 2^31-1 需改为 pair<int, long long>
vector<vector<pair<int, int>>> adj;
void add_edge(int x, int y, int z)
{
adj[x].push_back({y, z});
}
// 堆优化 Dijkstra，返回从起点 s 到各点（下标 1~tot）的最短距离，不可到达即为INF
// 【记录路径】需额外传入或声明：vector<int> prev(tot + 1, -1);
// 并在松弛成功处加：prev[y] = x;
// 回溯路径（以终点 t 为例）：
// vector<int> path;
// for (int i = t; i != -1; i = prev[i]) path.push_back(i);
// reverse(path.begin(), path.end()); // 此时 path 从起点到终点
vector<long long> dijkstra(int tot, int s)
{
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
vector<long long> dis(tot + 1, INF);
vector<bool> vis(tot + 1, false);
// vector<int> prev(tot + 1, -1); // 【记录路径】取消注释以启用
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
dis[s] = 0;
pq.push({0, s});
while (!pq.empty())
{
auto [_, x] = pq.top(); // _ 为当前节点已知最短距离，仅用于弹出，不参与后续计算
pq.pop();
if (vis[x])
continue;
vis[x] = true;
for (auto [y, z] : adj[x])
{
if (dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;
// prev[y] = x; // 【记录路径】取消注释以启用
pq.push({dis[y], y});
}
}
}
return dis;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
adj.assign(n + 1, {}); // 初始化邻接表，大小与节点数对应
// 读边示例（根据题目填写）：
// for (int i = 0; i < m; i++)
// {
// int x, y, w;
// cin >> x >> y >> w;
// add_edge(x, y, w);
// add_edge(y, x, w); // 若无向图加两次边
// }
// auto dis = dijkstra(n, 1);
system("pause");
return 0;
}
的SPFA（k为常数）
// 适用负权边，不适用负环，但是可以检测
#include <bits/stdc++.h>
using namespace std;
int n, m; // 节点数、边数，根据题目调整
// adj[u]：存储从 u 出发的有向边 {终点 v, 权值 w}，用于 SPFA
// 注意：权值为 int，若单条边权可能超过 2^31-1 需改为 pair<int, long long>
vector<vector<pair<int, int>>> adj;
void add_edge(int x, int y, int z)
{
adj[x].push_back({y, z});
}
// SPFA，返回从起点 s 到各点（下标 1~tot）的最短距离，不可到达即为 INF
// 若从 s 可达的范围内存在负环，返回空 vector
// 【记录路径】需额外传入或声明：vector<int> prev(tot + 1, -1);
// 并在松弛成功处加：prev[y] = x;
// 回溯路径（以终点 t 为例）：
// vector<int> path;
// for (int i = t; i != -1; i = prev[i]) path.push_back(i);
// reverse(path.begin(), path.end()); // 此时 path 从起点到终点
vector<long long> spfa(int tot, int s)
{
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
vector<long long> dis(tot + 1, INF);
vector<bool> in_queue(tot + 1, false);
vector<int> cnt(tot + 1, 0); // cnt[u]：节点 u 的入队次数，达到 tot 次说明存在负环
// vector<int> prev(tot + 1, -1); // 【记录路径】取消注释以启用
queue<int> q;
dis[s] = 0;
in_queue[s] = true;
cnt[s] = 1;
q.push(s);
while (!q.empty())
{
int x = q.front();
q.pop();
in_queue[x] = false;
for (auto [y, z] : adj[x])
{
if (dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;
// prev[y] = x; // 【记录路径】取消注释以启用
if (!in_queue[y])
{
q.push(y);
in_queue[y] = true;
if (++cnt[y] >= tot) // 入队次数达到节点总数，存在负环
return {};
}
}
}
}
return dis;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
adj.assign(n + 1, {}); // 初始化邻接表，大小与节点数对应
// 读边示例（根据题目填写）：
// for (int i = 0; i < m; i++)
// {
// int x, y, w;
// cin >> x >> y >> w;
// add_edge(x, y, w);
// add_edge(y, x, w); // 若无向图加两次边
// }
// auto dis = spfa(n, 1);
// if (dis.empty()) cout << "存在负环\n";
system("pause");
return 0;
}
(PS:之前一直忘了memset是对字节赋值，写出了"memset(dis,inf,sizeof(dis))"的惊人代码，死活调不对QAQ)
并查集实现kruskal
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
const int M=2*1e5+5;
const ll inf=0x7fffffff; //2147483647
const int mod=1e9+7;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={0,0,-1,0,1};
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0' && ch<='9'){x=(x<<3)+(x<<1);x+=(ch-'0');ch=getchar();}
return x*f;
}
void write(int x)
{
if (x<0) putchar('-'),x=-x;
if (x>10) write(x/10);
putchar(x%10+'0');
}
int n, m, f[N], ans, cnt;
struct Edge
{
int x,y,z;
}edge[M];
bool cmp(Edge a, Edge b){return a.z < b.z;}
int find(int x){return f[x] == x ? x : f[x]=find(f[x]);}
int main()
{
cin>>n>>m;
for (int i = 1; i <= n;i++) f[i] = i;
for (int i = 1;i <= m;i++)
{
cin>>edge[i].x>>edge[i].y>>edge[i].z;
}
sort(edge+1, edge+m+1, cmp);
for (int i = 1;i <= m;i++)
{
if (find(edge[i].x) ^ find(edge[i].y)) //两点不在同一路径上（同一个并查集里）
{
ans += edge[i].z;
f[find(edge[i].x)] = find(edge[i].y);
cnt++;
}
if (cnt == n-1)
break;
}
if (ans)
cout<<ans<<endl;
else
cout<<"orz\n";
system("pause");
return 0;
}