算法竞赛入门（c++实现）
【代码】算法竞赛入门。
·
零、前置
1. 头文件模板
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
#define endl '\n'
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<string, int> PSI;
// int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 5, MOD = 1e9 + 7;
LL mo(LL x) {return (x % MOD + MOD) % MOD;}
void oper()
{
return ;
}
int main()
{
IOS
int T = 1;
// cin >> T;
while (T --) oper();
return 0;
}
2. 解题思路
- 数据范围
- n <= 30，指数级别：DFS + 剪枝，状压DP
- n < 100，O(n ^ 3)：Floyd，DP，高斯消元
- n <= 1000，O(n ^ 2)，O(n ^ 2 * log n)：DP，二分，朴素Dijkstra，朴素Prim，Bellman-Ford
- n <= 10000，O(n * n ^ 1/2)：块状链表，分块，莫队
- n <= 100000，O(n * logn)：各种Sort，线段树，树状数组，Set/Map，Heap，拓扑排序，堆优化版Dijkstra，堆优化版Prim，Kruskal，Spfa，求凸包，求半平面交，二分，CDQ分治，整体二分，后缀数组，树链剖分，动态树
- n <= 1000000，O(n)，以及常数较小的O(n * logn)：单调队列，Hash，双指针扫描，BFS，并查集，KMP，AC自动机，Sort，树状数组，Heap，Dijkstra，Spfa
- n <= 10000000，O(n)：双指针扫描，KMP，AC自动机，线性筛素数
- n <= 1e9，O(n ^ 1/2)：判断质数
- n <= 1e18，O(logn)：最大公约数，快速幂，数位DP
- n <= 1e1000，O(logn ^ 2)：高精度加减乘除
- n <= 1e100000，O(logk * loglogk)，k表示位数，高精度加减，FFT/NTT
- 特殊情况
- 直接能 cout << 答案的情况
- 初始化情况
- 多组测试数据需要每次对相关变量置 0
- 边界情况
- 数组边界：a[0]，a[n]
- 对STL操作前判断非空
- 输出格式
- 行末空格
- Yes、YES 与 yes 的区别
- 优化
- 快读
- endl 替换为 ‘\n’
- for (auto &item : v) 取地址加快
一、基础算法
1. 前缀和
（1）一维前缀和
for (int i = 1; i <= n; i ++) prefix[i] = prefix[i - 1] + a[i];
cout << prefix[r] - prefix[l - 1] << endl;
（2）二维前缀和
// 初始化
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + a[i][j];
// 求区域和
cout << prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1] << endl;
// Tips：前缀和可能需要开 LL
2. 差分
（1）一维差分
// 初始化
for (int i = 1; i <= n; i ++) diff[i] = a[i] - a[i - 1];
// 修改 [l, r] 区间
diff[l] += x, diff[r + 1] -= x;
（2）二维差分
// 修改 (x1, y1, x2, y2) 区域
void modify(int x1, int y1, int x2, int y2, int c)
{
diff[x1][y1] += c;
diff[x2 + 1][y1] -= c;
diff[x1][y2 + 1] -= c;
diff[x2 + 1][y1 + 1] += c;
}
// 初始化
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
modify(i, j, i, j, a[i][j]);
// 修改区域
cin >> x1 >> y1 >> x2 >> y2 >> x;
modify(x1, y1, x2, y2, x);
// 后续前缀和处理
3. 二分
（1）整数二分
int l = 0, r = n - 1;
// 情况一：
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
// 情况二：
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
eles r = mid - 1;
}
// Tips：l = mid 时 l + r 要 + 1
（2）浮点数二分
double l = -100, r = 100;
while (r - l > 1e8)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
4. 位运算
// 与、或、非、位移、异或、取反
// lowbit：返回二进制中最后一个 1 的位置，用于树状数组
int lowbit(int x)
{
return x & -x;
}
// 相关推论：
1. 异或：（1）结合律、交换律（无分配率）
（2）a ^ 0 = a, a ^ a = 0
2. a + b = 2 * (a & b) + (a ^ b) => a + b >= a ^ b;
5. 排序
（1）sort排序
// 静态数组排序
sort(a, a + n);
// 动态数组排序
vector<int> v;
sort(v.begin(), v.end());
// 结构体排序
struct Book
{
int a, b, c;
bool operator < (const Book &E) const
{
if (a == E.a && b == E.b) return c > E.c;
else if (a == E.a) return b > E.b;
else return a > E.a;
}
}p[N];
sort(p, p + n);
// 排序去重
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
（2）桶排序
cin >> n;
int x;
for (int i = 0; i < n; i ++)
{
cin >> x;
cnt[x] ++;
}
for (int i = 0; i < 2e5 + 5; i ++)
{
while (cnt[i])
{
cout << i << ' ';
cnt[i] --;
}
}
6. 并查集
（1）朴素并查集（带路径压缩）
int find(int x) {return p[x] = p[x] == x ? x : find(p[x]);}
void merge(int a, int b)
{
p[find(a)] = find(b);
}
（2）可撤销并查集（空）
7. 高精度
// 高精度加法
vector<int> add(vector<int> A, vector<int> B)
{
vector<int> ans;
for (int i = 0, t = 0; i < A.size() || i < B.size() || t; i ++)
{
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
ans.push_back(t % 10);
t /= 10;
}
return ans;
}
// 高精度减法
bool cmp(vector<int> A, vector<int> B)
{
if (A.size() != B.size()) return A.size() > B.size();
else
{
for (int i = A.size() - 1; i >= 0; i --)
if (A[i] != B[i])
return A[i] > B[i];
}
return true;
}
vector<int> sub(vector<int> A, vector<int> B)
{
vector<int> ans;
for (int i = 0, t = 0; i < A.size(); i ++)
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
ans.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (ans.back() == 0 && ans.size() > 1) ans.pop_back();
return ans;
}
// 高精度乘法
vector<int> mul(vector<int> A, int b)
{
vector<int> ans;
for (int i = 0, t = 0; i < A.size() || t; i ++)
{
if (i < A.size()) t += A[i] * b;
ans.push_back(t % 10);
t /= 10;
}
while (ans.back() == 0 && ans.size() > 1) ans.pop_back();
return ans;
}
// 高精度除法
vector<int> div(vector<int> A, int b, int &r)
{
vector<int> ans;
r = 0;
for (int i = A.size() - 1; i >= 0; i --)
{
r = r * 10 + A[i];
ans.push_back(r / b);
r %= b;
}
reverse(ans.begin(), ans.end());
while (ans.back() == 0 && ans.size() > 1) ans.pop_back();
return ans;
}
// 初始化
string a;
vector<int> A;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
for (int i = ans.size() - 1; i >= 0; i --) cout << ans[i];
二、数据结构与STL
1. 栈、队列
queue<int> q;
q.pop();
q.front();
q.push();
q.size();
q.back()
q.empty();
stack<int> stk;
stk.push();
stk.top();
stk.pop();
stk.size();
stk.empty();
// Tips：queue，stack 无 clear 函数
2. 双端队列 Deque
deque<int> dq;
dq.size();
dq.empty();
dq.clear(); // 清空这个双端队列
dq.front(); // 返回第一个元素
dq.back(); // 返回最后一个元素
dq.push_back(); // 向最后插入一个元素
dq.pop_back(); // 弹出最后一个元素
dq.push_front(); // 向队首插入一个元素
dq.pop_front(); // 弹出第一个元素
dq.begin(); // 双端队列的第0个数
dq.end(); // 双端队列的最后一个的数的后面一个数
3. 优先队列（堆）
priority_queue<int> heap; // 大根堆
priority_queue<int, vector<int>, greater<int>> heap; // 小根堆
heap.top();
heap.pop();
heap.push();
heap.size();
heap.empty();
4. Map
map<int, int> mp;
unordered_map<int, int> mp;
map.size();
map.empty();
map.clear();
map.begin();
map.end(); // 支持++,--操作，返回前驱和后继
map.insert(); // 插入的是一个pair
map.erase(); // 输入的参数是pair或者迭代器
map.find();
map.lower_bound(x); // 返回大于等于x的最小的数的迭代器
map.upper_bound(x); // 返回大于x的最小的数的迭代器
5. Set
set<int> hash;
unordered_set<int> hash;
set.size();
set.empty();
set.clear();
set.begin();
set.end(); //支持++,--操作，返回前驱和后继
set.insert(); //插入一个数
set.find(); //查找一个数，若不存在返回end迭代器
set.count(); //返回某一个数的个数
set.erase(); //删除操作
set.erase(x); //输入一个数，删除所有x; O(k+logn);
set.erase(迭代器); //输入一个迭代器，删除这个迭代器
set.lower_bound(x); //返回大于等于x的最小的数的迭代器
set.upper_bound(x); //返回大于x的最小的数的迭代器
6. bitset
bitset<10000> vis;
vis.reset(); // 将所有位置为 0
vis.count(); // 返回 1 的个数
vis.any(); // 判断是否至少有一个 1
vis.none(); // 判断是否全为 0
// Tips：直接当做 bool 数组使用
7. 单调栈
// 表示每个元素的左边第一个比它小的元素
for (int i = 1; i <= n; i ++)
{
// 判断栈顶
while (stk.size() && stk.top() >= a[i]) stk.pop();
// 输出答案
if (stk.size()) cout << stk.top() << ' ';
else cout << -1 << ' ';
// 入栈
stk.push(a[i]);
}
8. 单调队列
for (int i = 1; i <= n; i ++)
{
// 队头处理
while (dq.size() && i - dq.front() + 1 > k) dq.pop_front();
// 队尾处理
while (dq.size() && a[dq.back()] < a[i]) dq.pop_back();
// 入队
dq.push_back(i);
// 输出答案
if (i >= k) cout << (dq.size() ? a[dq.front()] : -1) << " \n"[i == n];
}
9. 树状数组
// 单点修改
void update(int k, int x)
{
for (int i = k; i <= n; i += lowbit(i))
tr[i] += x;
}
// 区间查询
LL query(int x)
{
LL res = 0;
for (int i = x; i >= 1; i -= lowbit(i))
res += tr[i];
return res;
}
10. 朴素线段树
（1）加法线段树
LL a[N], tr[N * 4], lazy[N * 4]; // lazy 数组表示 u 当前节点还有任务需要下放
// 操作 u 号节点
void update(int st, int ed, int u, LL x)
{
lazy[u] += x;
tr[u] += (ed - st + 1) * x * 1LL;
}
// pushup 向上维护
void pushup(int u)
{
tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
// pushdown 向下更新
void pushdown(int st, int ed, int u)
{
if (lazy[u] == 0) return ; // 当前节点没有 lazy 下放
int mid = (st + ed) >> 1;
// 更新子节点的 lazy 和 tr
update(st, mid, u << 1, lazy[u]);
update(mid + 1, ed, u << 1 | 1, lazy[u]);
lazy[u] = 0; // 下放完毕
}
// 建树
void buildTree(int st = 1, int ed = n, int u = 1)
{
if (st == ed) // 叶子节点
{
tr[u] = a[st];
return ;
}
int mid = (st + ed) >> 1;
// 左右子树
buildTree(st, mid, u << 1);
buildTree(mid + 1, ed, u << 1 | 1);
pushup(u); // 左右子树构建完后要 pushup 更新父节点
}
// 区间修改
void modify(int l, int r, int u, int st, int ed, LL x)
{
if (st >= l && ed <= r) // 当前管辖区间完全包含于 [l, r]
{
update(st, ed, u, x);
return ;
}
pushdown(st, ed, u); // 向下走就要 pushdown
int mid = (st + ed) >> 1;
if (mid >= l) modify(l, r, u << 1, st, mid, x);
if (mid + 1 <= r) modify(l, r, u << 1 | 1, mid + 1, ed, x);
pushup(u); // 修改完子树就要 pushup
}
// 区间查询
LL query(int l, int r, int u, int st, int ed)
{
if (st >= l && ed <= r) return tr[u]; // 当前管辖区间完全包含于 [l, r]
pushdown(st, ed, u); // 向下走就要 pushdown
// 求子树之和
LL ans = 0;
int mid = (st + ed) >> 1;
if (mid >= l) ans += query(l, r, u << 1, st, mid);
if (mid + 1 <= r) ans += query(l, r, u << 1 | 1, mid + 1, ed);
return ans;
}
void oper()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++) cin >> a[i];
buildTree(); // 建树
int op, l, r;
LL x;
while (q --)
{
cin >> op;
if (op == 1)
{
cin >> l >> r >> x;
modify(l, r, 1, 1, n, x);
}
else
{
cin >> l >> r;
cout << query(l, r, 1, 1, n) << endl;
}
}
}
（2）最值线段树
LL a[N], trmax[N * 4], trmin[N * 4], lazy[N * 4]; // lazy 数组表示 u 当前节点还有任务需要下放
// 操作 u 号节点
void update(int st, int ed, int u, LL x)
{
lazy[u] += x;
trmax[u] += x;
trmin[u] += x;
}
// pushup 向上维护
void pushup(int u)
{
trmax[u] = max(trmax[u << 1], trmax[u << 1 | 1]);
trmin[u] = min(trmin[u << 1], trmin[u << 1 | 1]);
}
// pushdown 向下更新
void pushdown(int st, int ed, int u)
{
if (lazy[u] == 0) return ; // 当前节点没有 lazy 下放
int mid = (st + ed) >> 1;
// 更新子节点的 lazy 和 tr
update(st, mid, u << 1, lazy[u]);
update(mid + 1, ed, u << 1 | 1, lazy[u]);
lazy[u] = 0; // 下放完毕
}
// 建树
void buildTree(int st = 1, int ed = n, int u = 1)
{
if (st == ed) // 叶子节点
{
trmin[u] = trmax[u] = a[st];
return ;
}
int mid = (st + ed) >> 1;
// 左右子树
buildTree(st, mid, u << 1);
buildTree(mid + 1, ed, u << 1 | 1);
pushup(u); // 左右子树构建完后要 pushup 更新父节点
}
// 区间修改
void modify(int l, int r, int u, int st, int ed, LL x)
{
if (st >= l && ed <= r) // 当前管辖区间完全包含于 [l, r]
{
update(st, ed, u, x);
return ;
}
pushdown(st, ed, u); // 向下走就要 pushdown
int mid = (st + ed) >> 1;
if (mid >= l) modify(l, r, u << 1, st, mid, x);
if (mid + 1 <= r) modify(l, r, u << 1 | 1, mid + 1, ed, x);
pushup(u); // 修改完子树就要 pushup
}
// 区间查询
LL queryMax(int l, int r, int u, int st, int ed)
{
if (st >= l && ed <= r) return trmax[u]; // 当前管辖区间完全包含于 [l, r]
pushdown(st, ed, u); // 向下走就要 pushdown
// 求子树之和
LL ans = -INF;
int mid = (st + ed) >> 1;
if (mid >= l) ans = max(ans, queryMax(l, r, u << 1, st, mid));
if (mid + 1 <= r) ans = max(ans, queryMax(l, r, u << 1 | 1, mid + 1, ed));
return ans;
}
// 区间查询
LL queryMin(int l, int r, int u, int st, int ed)
{
if (st >= l && ed <= r) return trmin[u]; // 当前管辖区间完全包含于 [l, r]
pushdown(st, ed, u); // 向下走就要 pushdown
// 求子树之和
LL ans = INF;
int mid = (st + ed) >> 1;
if (mid >= l) ans = min(ans, queryMin(l, r, u << 1, st, mid));
if (mid + 1 <= r) ans = min(ans, queryMin(l, r, u << 1 | 1, mid + 1, ed));
return ans;
}
void oper()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++) cin >> a[i];
buildTree(); // 建树
int op, l, r;
LL x;
while (q --)
{
cin >> op;
if (op == 1)
{
cin >> l >> r >> x;
modify(l, r, 1, 1, n, x);
}
else
{
cin >> l >> r;
cout << queryMax(l, r, 1, 1, n) << ' ' << queryMin(l, r, 1, 1, n) << endl;
}
}
}
（3）异或线段树
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
#define endl '\n'
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<string, int> PSI;
// int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 5, MOD = 1e9 + 7;
LL mo(LL x) {return (x % MOD + MOD) % MOD;}
int n, q;
LL a[N], tr[N * 4], lazy[N * 4];
void update(int u, int st, int ed, LL x)
{
tr[u] ^= ((ed - st + 1) & 1) ? x : 0;
lazy[u] ^= x;
}
void pushdown(int u, int st, int ed)
{
if (lazy[u] == 0) return ;
int mid = st + ed >> 1;
update(u << 1, st, mid, lazy[u]);
update(u << 1 | 1, mid + 1, ed, lazy[u]);
lazy[u] = 0;
}
void pushup(int u)
{
tr[u] = tr[u << 1] ^ tr[u << 1 | 1];
}
void buildTree(int u, int st, int ed)
{
if (st == ed)
{
tr[u] = a[st];
return ;
}
int mid = st + ed >> 1;
buildTree(u << 1, st, mid);
buildTree(u << 1 | 1, mid + 1, ed);
pushup(u);
}
void modify(int u, int st, int ed, int l, int r, LL x)
{
if (l <= st && ed <= r)
{
update(u, st, ed, x);
return ;
}
pushdown(u, st, ed);
int mid = st + ed >> 1;
if (mid >= l) modify(u << 1, st, mid, l, r, x);
if (mid + 1 <= r) modify(u << 1 | 1, mid + 1, ed, l, r, x);
pushup(u);
}
LL query(int u, int st, int ed, int l, int r)
{
LL res = 0;
if (l <= st && ed <= r) return tr[u];
pushdown(u, st, ed);
int mid = st + ed >> 1;
if (mid >= l) res ^= query(u << 1, st, mid, l, r);
if (mid + 1 <= r) res ^= query(u << 1 | 1, mid + 1, ed, l, r);
return res;
}
void oper()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++) cin >> a[i];
buildTree(1, 1, n);
int op, l, r;
LL x;
while (q --)
{
cin >> op >> l >> r;
if (op == 1) // 异或
{
cin >> x;
modify(1, 1, n, l, r, x);
}
else // 求和
{
cout << query(1, 1, n, l, r) << endl;
}
}
return ;
}
int main()
{
IOS
int T = 1;
// cin >> T;
while (T --) oper();
return 0;
}
（4）线段树进阶（加法，乘法，赋值，求和）
// 取模函数
LL mo(LL x) {return (x % MOD + MOD) % MOD;}
int n, q;
LL a[N], tr[N * 4], mul[N * 4], add[N * 4]; // 定义操作为: tr * k + x
void update(int u, int st, int ed, LL k, LL x)
{
// (mul[u] * y + add[u]) * k + x ===> (mul[u] * k) * y + (add[u] * k + x)
tr[u] = mo(mo(tr[u] * k) + mo(x * (ed - st + 1)));
mul[u] = mo(mul[u] * k);
add[u] = mo(mo(add[u] * k) + x);
}
// 向上维护
void pushup(int u)
{
tr[u] = mo(tr[u << 1] + tr[u << 1 | 1]);
}
// 向下分发
void pushdown(int u, int st, int ed)
{
int mid = st + ed >> 1;
update(u << 1, st, mid, mul[u], add[u]);
update(u << 1 | 1, mid + 1, ed, mul[u], add[u]);
mul[u] = 1, add[u] = 0;
}
// 建树
void buildTree(int u, int st, int ed)
{
mul[u] = 1; // 初始化 mul 数组
if (st == ed)
{
tr[u] = a[st];
return;
}
int mid = st + ed >> 1;
buildTree(u << 1, st, mid);
buildTree(u << 1 | 1, mid + 1, ed);
pushup(u);
}
// 修改
void modify(int u, int st, int ed, int l, int r, LL k, LL x)
{
if (l <= st && ed <= r)
{
update(u, st, ed, k, x);
return ;
}
pushdown(u, st, ed);
int mid = st + ed >> 1;
if (mid >= l) modify(u << 1, st, mid, l, r, k, x);
if (mid + 1 <= r) modify(u << 1 | 1, mid + 1, ed, l, r, k, x);
pushup(u);
}
// 查询
LL query(int u, int st, int ed, int l, int r)
{
LL res = 0;
if (l <= st && ed <= r) return tr[u];
pushdown(u, st, ed);
int mid = st + ed >> 1;
if (mid >= l) res = mo(res + query(u << 1, st, mid, l, r));
if (mid + 1 <= r) res = mo(res + query(u << 1 | 1, mid + 1, ed, l, r));
return res;
}
void oper()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++) cin >> a[i];
buildTree(1, 1, n);
int op, l, r;
LL x;
while (q --)
{
cin >> op >> l >> r;
if (op == 1) // 加法
{
cin >> x;
modify(1, 1, n, l, r, 1, x);
}
else if (op == 2) // 乘法
{
cin >> x;
modify(1, 1, n, l, r, x, 0);
}
else if (op == 3) // 赋值
{
cin >> x;
modify(1, 1, n, l, r, 0, x);
}
else // 求和
{
cout << query(1, 1, n, l, r) << endl;
}
}
return ;
}
11. 权值线段树
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
#define endl '\n'
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<string, int> PSI;
// int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 5, MOD = 1e9 + 7;
LL mo(LL x) {return (x % MOD + MOD) % MOD;}
int q, tr[N * 4]; // 叶子节点tr[]存放的是个数
void pushup(int u)
{
tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
// 单点插入
void insert(int u, int st, int ed, int x)
{
if (st == ed)
{
tr[u] ++;
return ;
}
int mid = st + ed >> 1;
if (x <= mid) insert(u << 1, st, mid, x);
else insert(u << 1 | 1, mid + 1, ed, x);
pushup(u);
}
// 查询第 k 小（第 k 大）
int queryMin(int u, int st, int ed, int k)
{
if (st == ed) return st;
int left_sum = tr[u << 1], mid = st + ed >> 1;
if (k <= left_sum) return queryMin(u << 1, st, mid, k);
else return queryMin(u << 1 | 1, mid + 1, ed, k - left_sum);
}
// 查询区间内数的个数
int queryCnt(int u, int st, int ed, int l, int r)
{
if (l <= st && ed <= r) return tr[u];
int res = 0, mid = st + ed >> 1;
if (mid >= l) res += queryCnt(u << 1, st, mid, l, r);
if (mid + 1 <= r) res += queryCnt(u << 1 | 1, mid + 1, ed, l, r);
return res;
}
void oper()
{
cin >> q;
int n = N;
int op, l, r, x;
while (q --)
{
cin >> op;
if (op == 1) // 插入元素
{
cin >> x;
insert(1, 1, n, x);
}
else if (op == 2) // 查询个数
{
cin >> l >> r;
cout << queryCnt(1, 1, n, l, r) << endl;
}
else // 第 k 小
{
cin >> x;
cout << queryMin(1, 1, n, x) << endl;
}
}
return ;
}
int main()
{
IOS
int T = 1;
// cin >> T;
while (T --) oper();
return 0;
}
12. 主席树（可持久化权值线段树）
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
#define endl '\n'
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<string, int> PSI;
// int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 5, MOD = 1e9 + 7;
LL mo(LL x) {return (x % MOD + MOD) % MOD;}
vector<int> X;
LL bin(LL x) {return lower_bound(X.begin(), X.end(), x) - X.begin() + 1;};
struct Node
{
int ls, rs, val;
}tr[N << 5];
int n, q, idx, a[N], rt[N];
void insert(int st, int ed, int &u, int pre, int x)
{
u = ++ idx;
tr[u] = tr[pre];
tr[u].val ++;
if (st == ed) return ;
int mid = st + ed >> 1;
if (x <= mid) insert(st, mid, tr[u].ls, tr[pre].ls, x);
else insert(mid + 1, ed, tr[u].rs, tr[pre].rs, x);
}
LL queryVal(int st, int ed, int lu, int ru, int k)
{
if (st == ed) return st;
int mid = st + ed >> 1;
LL left_sum = tr[tr[ru].ls].val - tr[tr[lu].ls].val;
if (k <= left_sum) return queryVal(st, mid, tr[lu].ls, tr[ru].ls, k);
else return queryVal(mid + 1, ed, tr[lu].rs, tr[ru].rs, k - left_sum);
}
void oper()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++) cin >> a[i];
// 离散化
for (int i = 1; i <= n; i ++) X.push_back(a[i]);
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
for (int i = 1; i <= n; i ++) insert(1, n, rt[i], rt[i - 1], bin(a[i]));
int l, r, k;
while (q --)
{
cin >> l >> r >> k;
cout << X[queryVal(1, n, rt[l - 1], rt[r], k) - 1] << endl;
}
return ;
}
int main()
{
IOS
int T = 1;
// cin >> T;
while (T --) oper();
return 0;
}
13. 01Trie树（空）
三、搜索与图论
1. DFS
void dfs(int u, int b, int c) // 相关参数
{
// 退出条件
if (check())
{
ans ++; // 记录答案
return ;
}
// 改变状态
st[u] = true;
// 递归下一层
dfs(u + 1);
// 恢复现场
st[u] = false;
}
2. BFS
void bfs()
{
queue<int> q;
q.push(a); // 起点入队
// 判断队空
while (q.size())
{
// 队头出队
auto t = q.front();
q.pop();
// 处理队头
check();
// 新元素入队
q.push(x);
}
cout << ans << endl;
}
3. 最短路
（1）单源最短路（堆优化版 Dijkstra）
struct Edge
{
int a, w;
bool operator < (const Edge &E) const
{
return w > E.w;
}
};
int n, m, dist[N];
vector<Edge> v[N];
bitset<N> vis;
void dijkstra()
{
memset(dist, 0x3f, sizeof dist); // 初始化 dist 数组
dist[1] = 0; // 初始化起点
priority_queue<Edge> heap;
heap.push({1, dist[1]}); // 点和到点的距离
while (heap.size())
{
auto tt = heap.top();
int a = tt.a;
int w = tt.w;
heap.pop();
if (vis[a]) continue; // 冗余
vis[a] = true;
for (auto item : v[a])
{
int j = item.a;
int w = item.w;
if (dist[j] > dist[a] + w)
{
dist[j] = dist[a] + w;
heap.push({j, dist[j]});
}
}
}
if (dist[n] >= INF / 2) cout << -1 << endl;
else cout << dist[n] << endl;
}
// 初始化
void oper()
{
cin >> n >> m;
int a, b, w;
for (int i = 1; i <= m; i ++)
{
cin >> a >> b >> w;
v[a].push_back({b, w});
}
dijkstra();
}
（2）多源最短路（Floyd)
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
// 初始化
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i ++) g[i][i] = 0;
for (int i = 0; i < m; i ++)
{
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c); // 取最短边
}
// Tips：三层循环 k 在最外层
（3）带负权的单源最短路（BellmanFord）
（4）SPFA（队列优化版BellmanFord）
（5）带负权的全源最短路（Johnson）
4. 拓扑排序
vector<int> v[N]; // 存图
int d[N]; // 入度
vector<int> path; // 方案路径
void topsort()
{
queue<int> q;
// 入度为 0 的点入队
for (int i = 1; i <= n; i ++)
if (!d[i])
q.push(i);
while (q.size())
{
auto t = q.front();
q.pop();
path.push_back(t); // 记录路径
for (auto item : v[t])
{
d[item] --;
if (!d[item]) q.push(item); // 入度为 0 的点入队
}
}
// 判断答案合法性
if (path.size() == n)
for (auto item : path)
cout << item << ' ';
else
cout << -1 << endl;
}
5. 最小生成树（Kruskal）
struct Edge
{
int a, b;
LL w;
bool operator < (const Edge &E) const
{
return w < E.w;
}
};
vector<Edge> v;
int p[N];
int find(int x) {return p[x] = p[x] == x ? x : find(p[x]);}
void kruskal()
{
for (int i = 1; i <= n; i ++) p[i] = i; // 初始化并查集
sort(v.begin(), v.end()); // 对边排序
int cnt = 1;
LL ans = 0;
for (int i = 0; i < v.size(); i ++)
{
auto t = v[i];
int a = t.a, b = t.b;
LL w = t.w;
if (find(a) != find(b))
{
p[find(a)] = find(b);
cnt ++;
ans += w;
}
}
if (cnt == n) cout << ans << endl;
else cout << -1 << endl;
}
6. LCA
int depth[N], fa[N][30]; // fa[i][j] 表示 i 号节点向上走 2 ^ j 格
vector<int> g[N];
// 初始化 fa 与 depth 数组
void dfs(int u)
{
depth[u] = depth[fa[u][0]] + 1; // 记录当前深度
for (int i = 1; i <= 20; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
// 遍历儿子节点
for (auto &item : g[u]) dfs(item);
}
// 求 lca
int lca(int x, int y)
{
if (depth[x] <= depth[y]) swap(x, y); // 保持 x 在下方
// 若 x 向上跳，挑了还比 y 更深，则跳
for (int i = 20; i >= 0; i --)
if (depth[fa[x][i]] >= depth[y])
x = fa[x][i];
if (x == y) return x; // x 与 y 在同一层
for (int i = 20; i >= 0; i --)
{
if (fa[x][i] == fa[y][i]) continue;
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
void oper()
{
cin >> n;
for (int i = 2; i <= n; i ++)
{
cin >> fa[i][0];
g[fa[i][0]].push_back(i); // 父节点 -> i 连边
}
dfs(1);
cin >> q;
int x, y;
while (q --)
{
cin >> x >> y;
cout << lca(x, y) << endl;
}
}
// 推论：
// (1) u -> v 的简单路径 = 两条链：u -> LCA(u, v) 和 LCA(u, v) -> v
// (2) LCA(x, y, z) = LCA(x, LCA(y, z)) = LCA(LCA(x, y), z) 类似 max, min, gcd
// (3) LCA(x1, x2, x3, x4 ... xk) = LCA(dfs序最小点, dfs序最大点)
7. Tarjan（空）
（1）Tarjan求LCA（空）
（2）Tarjan找环（空）
（3）Tarjan求有向图缩点（空）
（4）Tarjan求无向图求割点、割边（空）
四、数论
1. 试除法
bool is_prime(int n)
{
if (n < 2) return false;
for (int i = 2; i <= n / i; i ++)
if (n % i == 0)
return false;
return true;
}
2. 埃氏筛
LL n;
bitset<N> vis; // vis = 1 表示为合数，vis = 0 表示为质数
void oper()
{
cin >> n;
vis[0] = vis[1] = 1; // 将合数标记为1
for (LL i = 2; i <= n; i ++)
if (!vis[i]) // 若当前为质数，则将范围内所有质数的倍数标记为合数
for (LL j = i * 2; j <= n; j += i)
vis[j] = 1;
for (LL i = 1; i <= n; i ++)
if (!vis[i])
cout << i << ' ';
}
3. gcd 与 lcm
LL a, b;
void oper()
{
cin >> a >> b;
cout << __gcd(a, b) << ' '; // 最大公约数
cout << a * b / __gcd(a, b) << endl; // 最小公倍数
}
4. 快速幂与逆元
LL qmi(LL a, LL k, LL p) // 求 a ^ k % p
{
LL res = 1;
while (k)
{
if (k & 1) res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}
// 逆元
auto t = qmi(a, p - 2, p);
if (a % p != 0) cout << t << endl;
else cout << "impossible" << endl;
5. 组合数（进阶）
const int MOD = 1e9 + 7;
LL fact[N], infact[N];
LL qmi(LL a, LL k, LL p) // 快速幂
{
LL res = 1;
while (k)
{
if (k & 1) res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}
LL C(int n, int m) // 求 C(n, m) = n! / [(n - m) ! * m!] 即 fact[n] * infact[n - m] % MOD * infact[m] % MOD
{
return fact[n] * infact[m] % MOD * infact[n - m] % MOD;
}
void init(int n) // 初始化 fact 与 infact 数组
{
fact[0] = 1;
for (int i = 1; i <= n; i ++) fact[i] = (LL)fact[i - 1] * i % MOD;
infact[n] = qmi(fact[n], MOD - 2, MOD);
for (int i = n - 1; i >= 0; i --) infact[i] = (LL)infact[i + 1] * (i + 1) % MOD;
}
五、动态规划
1. 背包问题
（1）01背包
for(int i = 1; i <= n; i ++)
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
（2）完全背包
for(int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
（3）多重背包（二进制优化）
int a, b, s, cnt = 0; // 每种物品的体积，价格，数量，二进制打包后总物品种数
for (int i = 0; i < n; i ++)
{
cin >> a >> b >> s;
int k = 1;
while (s >= k)
{
++ cnt; // 先自增，再使用
v[cnt] = k * a;
w[cnt] = k * b;
s -= k;
k *= 2;
}
if (s)
{
++ cnt;
v[cnt] = s * a;
w[cnt] = s * b;
}
}
// 01 背包
for (int i = 1; i <= cnt; i ++)
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
（4）分组背包
for (int i = 1; i <= n; i ++)
for (int j = m; j >= 0; j --)
for (int k = 1; k <= s[i]; k ++)
if (v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
2. 线性DP
最长上升子序列（LIS）
for (int i = 1; i <= n; i ++)
{
f[i] = 1;
for (int j = 1; j <= i; j ++)
if (a[j] < a[i]) // 注意是否为 严格递增 或 单调不减
f[i] = max(f[i], f[j] + 1);
}
cout << *max_element(f + 1, f + 1 + n) << endl;
3. 区间DP
// dp[l, r] 拆分为 dp[l, k - 1] 与 dp[k - 1, r]
4. 树形DP
// 配合dfs
六、常用库
// 向上取整
(a + b - 1) / b
// 四舍五入
round()
// 进制转换
string s;
cin >> s;
char *c;
cout << strtol(s.c_str(), &c, 10) << endl;
// pi
acos(-1.0)
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
23
0- 0
已为社区贡献1条内容
所有评论(0)