标记永久化
最开始我以为标记永久化只是 Lazy-tag 的替代品，但它真的很好用。
原理
在应用 Lazy-tag 技术的线段树中，查询时将所有包含在查询区间的小区间答案合并，一段区间的答案被直接保存在该区间节点内。为了达到这个目的，每次访问某个区间时，先利用 push_down 函数将该区间的正确答案计算出来（表现为将该节点到根节点路径上所有操作累加到该节点）。
标记永久化则没有 push_down 函数，但将 push_down 原本的功能转移到了查询函数，具体：
- 更新时，更新到包含在内的最大区间（与传统线段树一样，只是没有
puhs_down）。 - 查询时，将查询路径上所有点上的答案累加。
以区修单查区间最值为例（这是标记永久化最自然的一种应用）：
int tg[]; // 只需要维护tg一个数组
void upd(int u,int l,int r,int ql,int qr,int v) {if (ql <= l && r <= qr) return tg[u] = max(tg[u],v),void();int mid = (l + r) >> 1;if (ql <= mid) upd(ls(u),l,mid,ql,qr,v);if (qr > mid) upd(rs(u),mid + 1,r,ql,qr,v);
}
int qry(int u,int l,int r,int p,int v) {if (l == r) return tg[u];int mid = (l + r) >> 1,ans = tg[u]; // 注意到累计每一层if (p <= mid) ans = min(ans,qry(ls(u),l,mid,p,v));else ans = min(ans,qry(rs(u),mid + 1,r,p,v));return ans;
}
对于区间修改区间查询，就不能只维护 tag，还需要维护节点子树内所有标记构成的区间和 sum。
通过 push_up 维护 sum，显然可以得出：
\[sum_p=sum_{ls(p)}+sum_{rs(p)}+len\cdot tag_p
\]
即：左右儿子贡献和自己直接的贡献。
int tg[],sum[];
void push_up(int u,int l,int r) {sum[u] = sum[ls(u)] + sum[rs(u)] + (r - l + 1) * tg[u];
}
void upd(int u,int l,int r,int ql,int qr,int v) {if (ql <= l && r <= qr) {tg[u] += v;sum[u] += v * (r - l + 1);return ;}int mid = (l + r) >> 1;if (ql <= mid) upd(ls(u),l,mid,ql,qr,v);if (qr > mid) upd(rs(u),mid + 1,r,ql,qr,v);push_up(u,l,r);
}
int qry(int u,int l,int r,int p,int v,int fa) { // fa: 来自祖先的标记if (ql <= l && r <= qr) return sum[u] + fa * (r - l +1 );int mid = (l + r) >> 1,ans = 0; // 注意到累计每一层 fa + tg[u]if (p <= mid) ans += qry(ls(u),l,mid,p,v,fa + tg[u]);else ans += ans,qry(rs(u),mid + 1,r,p,v,fa + tg[u]);return ans;
}
重点应用
扫描线
需先了解扫描线原理。
我们需要维护一个序列，这个序列所有至少被一个矩形覆盖的区间。
记 cnt 为区间被矩形完全覆盖的次数，\(sum\) 表示该区间答案，则有：
- \(cnt>0\) 时，直接返回区间长度（离散值还原后）。
- \(cnt=0\) 时，统计左右儿子答案，
push_up汇总到 \(sum\)。
这是一个很显然的标记永久化，因为 cnt 不下传，只停留在一开始的区间。
struct SGT {
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)struct node { int len,cnt; // 非0的长度,全区间被覆盖的次数 };node tr[4 * maxn + 5];inline void push_up(int u,int l,int r) {if (tr[u].cnt > 0) tr[u].len = pos[r] - pos[l];else tr[u].len = tr[lson(u)].len + tr[rson(u)].len;}void update(int u,int l,int r,int ql,int qr,int val) {if (ql <= l && r <= qr) {tr[u].cnt += val;push_up(u,l,r);return ;}int mid = (l + r) >> 1;if (qr <= mid) update(lson(u),l,mid,ql,qr,val);else if (ql >= mid) update(rson(u),mid,r,ql,qr,val);else update(lson(u),l,mid,ql,mid,val),update(rson(u),mid,r,mid,qr,val);push_up(u,l,r);}
};
例题
（咕咕咕……—— Denia-kawaii）