1. 模板 int n; vector<int> tree; int lowbit(int x) { return x & -x; } int query(int x) { int ans = 0; for(int i = x; i > 0; i -= lowbit...
Segement Tree
你要不嫌麻烦, 不怕代码量大, 面对几乎一切有关区间信息维护的问题, 你都可以用线段树解决. 毕竟, 它可以实现 $O(\log{N})$ 的区间修改, 区间查询. 上面说的区间, 当然也包括单点这个特例. 上面说的查询, 不仅包括区间和, 区间最值也行. 换言之, 只要你维护该区间的信息能够通过左右孩子结点表达, 那么这个信息都能够通过线段树维护. 大致思想 线段树通常采用堆...
FenwickTree
struct FenwickTree { vector<int> bit; // binary indexed tree int n; FenwickTree(int n) { this->n = n; bit.assign(n, 0); } FenwickTree(vector<int&g...
Dijkstra
1. 暴力法 - 适用于稠密图 int n = 1000, k = 3; const int inf = INT_MAX / 2; // 任意两个节点的初始距离是: 无穷大 vector<vector<int>> adj(n, vector<int>(n, inf)); // 直接相连的节点, 距离设为链路权重 ...
DSU 并查集
1. 模板 #include <bits/stdc++.h> using namespace std; struct DSU { vector<int> parent; void init(int k) { // 0 or 1-index ? parent.resize(k + 1); for...
DFS时间戳
1.何为时间戳? 我们可以在 DFS 一棵树的过程中, 维护一个全局的时间戳 clock, 每访问一个新的节点, 就将 clock 加一 同时, 记录进入节点 x 时的时间戳 in[x], 和离开(递归结束)这个节点时的时间戳 out[x] 2.性质? 当我们递归以 x 为根的子树时, 设 y 是以 xx 为根的子树中的一个节点, 那么我们必须先递归完以 y 为根的子树, 之后才能递...
01BFS
1. 0-1 BFS 0-1 BFS 教程 - codeforces 1368: 使网格图至少有一条有效路径的最小代价 2290: 到达角落需要移除障碍物的最小数目 using PII = pair<int, int>; class Solution { private: static constexpr int dirs[4][2] = {{0, 1}, {0...
Writing a New Post
This post will guide you how to write a post on Chirpy theme. Even if you have previous experience with Jekyll, this article is worth reading, because many features require specific variables to be...
Text and Typography
This post is to show Markdown syntax rendering on Chirpy, you can also use it as an example of writing. Now, let’s start looking at text and typography. Lists Description list Sun the star ...
Recently Updated