「v4」0x40 数据结构
同步于 2026-11-11,花费 14,451,581 tok。
0x41 数据结构 序列结构
ST 表
0x41 ST 表.cpp:
// ST 表
template <class T, auto op>
struct SparseTable {
int t;
std::vector<std::vector<T>> f;
SparseTable() {}
SparseTable(int n, const std::vector<T> &a) {
init(n, a);
}
void init(int n, const std::vector<T> &a) {
t = std::__lg(n);
f.assign(t + 1, std::vector<T>(n + 1));
for (int i = 1; i <= n; i ++) {
f[0][i] = a[i];
}
for (int j = 1; j <= t; j ++) {
for (int i = 1; i <= n - (1 << j) + 1; i ++) {
f[j][i] = op(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
}
}
}
T ask(int l, int r) {
int k = std::__lg(r - l + 1);
return op(f[k][l], f[k][r - (1 << k) + 1]);
}
};并查集
0x41 可撤销并查集.cpp:
// 可撤销并查集
struct DSU {
std::vector<int> sze;
std::vector<int> fa;
std::vector<std::pair<int, int>> his;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
sze.assign(n + 1, 1);
fa.resize(n + 1);
std::iota(fa.begin(), fa.end(), 0);
his.clear();
}
int get(int x) {
return fa[x] == x ? x : get(fa[x]); // 按秩合并不能路径压缩
}
bool merge(int x, int y) {
int p = get(x), q = get(y);
if (p == q) {
return 0;
}
if (sze[p] > sze[q]) {
std::swap(p, q);
}
his.push_back({p, q});
sze[q] += sze[p], fa[p] = q;
return 1;
}
int time() {
return his.size();
}
void revert(int tim) {
while (his.size() > tim) {
auto [p, q] = his.back(); his.pop_back();
sze[q] -= sze[p], fa[p] = p;
}
}
};线段树
扫描线
势能线段树
区间开平方:一个整数 x 开平方 \mathcal{O}(\log \log V) 次之后就会变成 1。若区间 \mathrm{max} = 1 则 return。
区间取模:一个整数 x (x \ge p) 对 p 取模,x 至少变小一半。若区间 \mathrm{max} < p 则 return。
区间除法:整除 p 之后,由于 \lfloor \frac{\max}{p} \rfloor - \lfloor \frac{\min}{p} \rfloor \leq \lceil \frac{\max - \min}{p} \rceil,区间最大值与最小值的差,多数情况下会减半。
- 若区间 \mathrm{max} - \mathrm{min} = 0,则区间加之后
return。 - 若区间 \mathrm{max} - \mathrm{min} = 1 且 \lfloor \frac{\mathrm{\max}}{p} \rfloor \neq \lfloor \frac{\mathrm{\min}}{p} \rfloor,则区间加之后
return。
区间按位与:一个二进制数 x 与 v 进行按位与,至多进行 \log V 次有效操作。若区间(在二进制下)\mathrm{bitor} \subseteq v 则 return。
区间取最值(吉老师线段树):以区间取最小值为例:
- 在线段树上的每一个节点 p 需要维护:
mx:区间最大值。cnt:区间最大值个数。md:区间严格次大值。
- 在区间修改时,若遇到一个“被询问区间完全覆盖的节点”时:
- 若 x \geq \mathrm{mx},则
return。 - 若 x \leq \mathrm{md},则暴力递归左右儿子修改。
- 若 \mathrm{md} < x < \mathrm{mx},则有 \mathrm{cnt} 个 \mathrm{mx} 被修改成 x,打标记后
return。
- 若 x \geq \mathrm{mx},则
- 时间复杂度 \mathcal{O}(n \log^2 n)。
0x41 吉老师线段树.cpp:
struct Info {
int mx, md;
int cnt;
Info() {}
Info(int mx, int md, int cnt) : mx(mx), md(md), cnt(cnt) {}
friend Info operator + (Info l, Info r) {
if (l.mx == r.mx) {
return Info(l.mx, std::max(l.md, r.md), l.cnt + r.cnt);
} else if (l.mx > r.mx) {
return Info(l.mx, std::max(l.md, r.mx), l.cnt);
} else {
return Info(r.mx, std::max(l.mx, r.md), r.cnt);
}
}
};
// 吉老师线段树
namespace SGT {
struct node {
int len;
i64 sum;
Info info;
int add; // 加法标记(初始值等于 0)
int tag; // 区间取 min 标记(初始值等于 +inf,需要根据数据范围修改)
void mk_add(int x) {
sum += 1ll * x * len;
info.mx += x;
if (info.md != -inf) info.md += x;
add += x;
if (tag < inf) tag += x;
}
void mk_tag(int x) {
if (info.mx <= x) return;
sum -= 1ll * (info.mx - x) * info.cnt;
info.mx = x;
tag = x;
}
} t[N * 4];
void upd(int p) {
t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
t[p].info = t[p * 2].info + t[p * 2 + 1].info;
}
void spread(int p) {
if (t[p].add) {
t[p * 2].mk_add(t[p].add), t[p * 2 + 1].mk_add(t[p].add);
t[p].add = 0;
}
if (t[p].tag < inf) {
t[p * 2].mk_tag(t[p].tag), t[p * 2 + 1].mk_tag(t[p].tag);
t[p].tag = inf;
}
}
void build(int p, int l, int r) {
t[p].add = 0, t[p].tag = inf, t[p].len = r - l + 1;
if (l == r) {
t[p].sum = a[l], t[p].info = Info(a[l], -inf, 1);
return;
}
int mid = (l + r) >> 1;
build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
upd(p);
}
void change_add(int p, int l, int r, int s, int e, int x) {
if (s <= l && r <= e) {
t[p].mk_add(x);
return;
}
spread(p);
int mid = (l + r) >> 1;
if (s <= mid) {
change_add(p * 2, l, mid, s, e, x);
}
if (mid < e) {
change_add(p * 2 + 1, mid + 1, r, s, e, x);
}
upd(p);
}
void change_min(int p, int l, int r, int s, int e, int x) {
if (s <= l && r <= e && t[p].info.md < x) {
t[p].mk_tag(x);
return;
}
spread(p);
int mid = (l + r) >> 1;
if (s <= mid) {
change_min(p * 2, l, mid, s, e, x);
}
if (mid < e) {
change_min(p * 2 + 1, mid + 1, r, s, e, x);
}
upd(p);
}
}