外观
线段树板子
维护群 (T,⊕),⊕ 有单位元 O,懒标记信息为 STAT
struct segtree {
// === 数据 ===
T a[maxn * 4];
STAT lz[maxn * 4];
// === 辅助函数 ===
inline int lc(int x) { return x<<1; }
inline int rc(int x) { return (x<<1) | 1; }
inline int md(int x, int y) { return (x+y)>>1; }
// === 维护 ===
inline void pushup(int tn) {
a[tn] = a[lc(tn)] ⊕ a[rc(tn)];
}
inline void pushdown(int tn) {
int lcn=lc(tn), rcn=rc(tn);
update a[lcn], lz[lcn] with lz[tn];
update a[rcn], lz[rcn] with lz[tn];
// 取决于具体懒标记类型
lz[tn] = CLEAR;
}
// === 建树 ===
void build(int tn, int tl, int tr) {
if (tl == tr) {
a[tn] = get(tl);
return;
}
int mid = md(tl, tr);
build(lc(tn), tl, mid);
build(rc(tn), mid+1, tr);
pushup(tn);
}
// === 单点操作 ===
void modify1(int tn, int tl, int tr, int i, MODIFY m) {
if (tl == tr) {
modify a[tn] with m;
return;
}
pushdown(tn);
int mid = md(tl, tr); // 谁懂整天写成 md(x,y) 的救赎感
if (i <= mid) {
modify1(lc(tn), tl, mid, i, m);
} else {
modify1(rc(tn), mid+1, tr, i, m);
}
pushup(tn);
}
T query1(int tn, int tl, int tr, int i) {
if (tl == tr) {
return a[tn];
}
pushdown(tn);
int mid = md(tl, tr);
if (i <= mid) {
return query1(lc(tn), tl, mid, i);
} else {
return query1(rc(tn), mid+1, tr, i);
}
}
// === 区间操作 ===
void modify2(int tn, int tl, int tr, int x, int y, MODIFY m) {
if (y < tl || tr < x) {
return;
}
if (x <= tl && tr <= y) {
MODIFY a[tn] with m;
MODIFY lz[tn] with m;
return;
}
pushdown(tn);
int mid = md(tl, tr);
modify2(lc(tn), tl, mid, x, y, m);
modify2(rc(tn), mid+1, tr, x, y, m);
pushup(tn);
}
T query2(int tn, int tl, int tr, int x, int y) {
if (y < tl || tr < x) {
return O;
}
if (x <= tl && tr <= y) {
return a[tn];
}
pushdown(tn);
int mid = md(tl, tr);
return (
query2(lc(tn), tl, mid, x, y, m)
⊕ query2(rc(tn), mid+1, tr, x, y, m)
);
}
} sgt;总结:
- 细分操作前
pushdown; - 细分修改后
pushup; - 区间操作特判包含/不交;
- 单点操作特判区间缩成点。
- 以及,
md(x,y)打得太顺手了……