【题解】可持久化区间仿射区间和（Persistent Range Affine Range Sum）-北京尧图网络

很好小朋友们我们被要求写一个可持久化线段树支持区间修改、区间复制和输出区间和。懒标记是必须的但可持久化线段树一般不太支持 pushdown尤其在本题中。在进入子节点之前我们需要克隆当前节点因为当前节点可能被其他版本共享。然后才能将其懒标记下推到新克隆出的子节点最后将当前节点的懒标记重置。这样会导致不必要的新节点开销。于是我们不考虑 pushdown而是在递归函数中同时传进祖先变化即懒标记。线段树维护五个参数分别是左右子节点、区间总和 b、c 懒标记。1处理操作 0我们构建一个 change 函数对版本 p 的区间 [l, r] 施加变换 x - b*x c返回新版本的根节点。可持久化的精髓是“改了才新建”编写时请注意祖先变化的传递。2处理操作 1一个个复制绝对是不明智的我们可以先构建一个 crossover 函数。合并两个版本 x 和 y返回一个新版本其前 at 个元素来自 x后 len - at 个元素来自 y。这样题目的 [l, r] 可以变成先处理 [1, r] 的复制接着把原来的 [1, l - 1] 复制回去。3处理操作 2正常的 query 函数即可。另注意本题的边界和 base 十分复杂我用的是统一 base-1。#include bits/stdc.h using namespace std; typedef long long LL; const LL P 998244353; // 模数 const int N 1e5 10; // 数组最大长度 #define lc(p) tr[p].lc // 左孩子下标 #define rc(p) tr[p].rc // 右孩子下标 #define MID ((L R) 1) // 当前区间中点 /* 线段树节点结构 lc, rc : 左右孩子指针下标 sum : 当前节点代表的区间和已应用该节点的懒标记 lazy_b, lazy_c : 懒标记表示对子区间施加的仿射变换 x - lazy_b * x lazy_c */ struct node { int lc, rc; LL sum; LL lazy_b, lazy_c; }; vectornode tr; // 动态存储所有节点0 号节点为空节点 LL a[N]; // 原始数组1‑based // 新建一个节点懒标记初始为恒等变换 (1, 0) int newd() { tr.push_back({0, 0, 0, 1, 0}); return (int)tr.size() - 1; } // 克隆节点 p复制其所有信息 int clone_node(int p) { tr.push_back(tr[p]); return (int)tr.size() - 1; } /* 将仿射变换 x - b*x c 应用到节点 p 所代表的整个区间长度为 len 同时更新该节点的懒标记使其与原有懒标记复合。注意应用顺序为新变换作用于旧变换即最终变换为 b*(old(x)) c。 */ void modify(int p, LL b, LL c, LL len) { if (p 0) return; tr[p].sum (b * tr[p].sum c * len) % P; tr[p].lazy_b b * tr[p].lazy_b % P; tr[p].lazy_c (b * tr[p].lazy_c % P c) % P; } // 复合变换返回 g(f())即先 f 后 g pairLL, LL compose(LL g_b, LL g_c, LL f_b, LL f_c) { return { (g_b * f_b) % P, (g_b * f_c g_c) % P }; } // 用左右子树的 sum 更新当前节点的 sum void pushup(int p) { tr[p].sum (tr[lc(p)].sum tr[rc(p)].sum) % P; } // 建树p 为引用返回根节点下标 void build(int p, int L, int R) { p newd(); if (L R) { tr[p].sum a[L] % P; return; } build(lc(p), L, MID); build(rc(p), MID 1, R); pushup(p); } /* 对版本 p 的区间 [l, r] 施加变换 x - b*x c返回新版本的根节点。参数 prop_b, prop_c 表示从根到当前节点路径上所有祖先懒标记复合后的变换需要在访问当前区间时应用。本函数采用路径复制只修改必要的节点保留未修改部分。 */ int change(int p, int L, int R, int l, int r, LL b, LL c, LL prop_b, LL prop_c) { // 完全不相交克隆当前节点并应用祖先变换然后返回 if (r L || R l) { int np clone_node(p); modify(np, prop_b, prop_c, R - L 1); return np; } // 完全覆盖克隆当前节点整体施加 “祖先变换当前变换” if (l L R r) { auto t compose(b, c, prop_b, prop_c); // 先 prop后 (b,c) int np clone_node(p); modify(np, t.first, t.second, R - L 1); return np; } // 部分重叠创建新节点懒标记为恒等 int np newd(); // 传递给子节点的祖先变换 prop ∘ p.lazy先 p.lazy后 prop auto t compose(prop_b, prop_c, tr[p].lazy_b, tr[p].lazy_c); // 左子区间有重叠递归处理 if (l MID) { lc(np) change(lc(p), L, MID, l, r, b, c, t.first, t.second); } else { // 左子区间没有重叠克隆并应用祖先变换 if (lc(p) ! 0) { int lc clone_node(lc(p)); modify(lc, t.first, t.second, MID - L 1); lc(np) lc; } } // 右子区间有重叠递归处理 if (r MID 1) { rc(np) change(rc(p), MID 1, R, l, r, b, c, t.first, t.second); } else { if (rc(p) ! 0) { int rc clone_node(rc(p)); modify(rc, t.first, t.second, R - (MID 1) 1); rc(np) rc; } } pushup(np); return np; } // 封装 update - change初始祖先变换为恒等 int update(int p, int L, int R, int l, int r, LL b, LL c) { return change(p, L, R, l, r, b, c, 1, 0); } /* 合并两个版本 x 和 y返回一个新版本其前 at 个元素来自 x后 len - at 个元素来自 y。参数 xb,xc 和 yb,yc 分别为两个版本当前需要应用的祖先变换。具体规则 - at 0 全部取 y - at len 全部取 x - 否则根据 at 与左子树长度的关系递归处理左右子树。 */ int crossover(int x, int y, int len, int at, LL xb, LL xc, LL yb, LL yc) { if (at 0) { // 全部来自 y if (y 0) return 0; int ny clone_node(y); modify(ny, yb, yc, len); return ny; } if (len at) { // 全部来自 x if (x 0) return 0; int nx clone_node(x); modify(nx, xb, xc, len); return nx; } int midl (len 1) 1; // 左子树长度尽量平衡 // 为啥是上取整len R - L 1 // MID (R L) / 2 // midl MID - L 1 // 2 * midl R L - 2 * L 2 * 1 // midl R - L 1 LL nx_b, nx_c, ny_b, ny_c; // 将 x 的祖先变换与其自身懒标记复合得到传递给左/右子树的变换 if (x ! 0) { auto res compose(xb, xc, tr[x].lazy_b, tr[x].lazy_c); nx_b res.first; nx_c res.second; } else { nx_b xb; nx_c xc; } if (y ! 0) { auto res compose(yb, yc, tr[y].lazy_b, tr[y].lazy_c); ny_b res.first; ny_c res.second; } else { ny_b yb; ny_c yc; } int left_x (x 0) ? 0 : lc(x); int left_y (y 0) ? 0 : lc(y); int right_x (x 0) ? 0 : rc(x); int right_y (y 0) ? 0 : rc(y); // 左子树需要的前 at 个元素来自 x int lc crossover(left_x, left_y, midl, at, nx_b, nx_c, ny_b, ny_c); // 右子树需要的前 at - midl 个元素来自 x int rc crossover(right_x, right_y, len - midl, at - midl, nx_b, nx_c, ny_b, ny_c); int res newd(); lc(res) lc; rc(res) rc; pushup(res); return res; } /* 操作 1 的封装将版本 y 的区间 [l, r] 复制到版本 x 的对应位置。通过两次交叉实现 1. tmp x[0 : l - 1] y[l : n] 2. 结果 tmp[0 : r] x[r : n] x[0 : l - 1] y[l : r] x[r : n] */ int update_crossover_twice(int x, int y, int l, int r, int total_len) { int tmp crossover(x, y, total_len, l - 1, 1, 0, 1, 0); return crossover(tmp, x, total_len, r, 1, 0, 1, 0); } /* 查询版本 p 中区间 [l, r] 的和。参数 b, c 表示当前路径上所有祖先懒标记复合后的变换在完全覆盖时直接应用到当前节点的 sum 上。 */ LL query(int p, int L, int R, int l, int r, LL b, LL c) { if (r L || R l) { return 0; } if (l L R r) { return (b * tr[p].sum c * (R - L 1)) % P; } // 传递给子节点的祖先变换 (b,c) ∘ p.lazy先 p.lazy后当前祖先 auto t compose(b, c, tr[p].lazy_b, tr[p].lazy_c); LL res 0; res query(lc(p), L, MID, l, r, t.first, t.second); res query(rc(p), MID 1, R, l, r, t.first, t.second); return res % P; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, Q; cin n Q; for (int i 1; i n; i ) cin a[i]; tr.reserve(20000000); // 预留节点空间 tr.push_back({0, 0, 0, 1, 0}); // 0 号节点作为空节点 int rt; build(rt, 1, n); vectorint roots(Q 1); // roots[i] 存储版本 A_i 的根节点 roots[0] rt; // 初始版本 A_{-1} for (int i 1; i Q; i) { int opt; cin opt; // 输入中 k, s 为 0‑based 版本编号-1 表示初始版本所以用 k1 索引 roots if (opt 0) { // 区间仿射变换 int k, l, r; LL b, c; cin k l r b c; l ; // 输入区间为 [l, r) 的 0‑based 下标转为 1‑based int src roots[k 1]; roots[i] update(src, 1, n, l, r, b, c); } else if (opt 1) { // 区间从另一版本复制 int k, s, l, r; cin k s l r; l ; int src_k roots[k 1]; int src_s roots[s 1]; roots[i] update_crossover_twice(src_k, src_s, l, r, n); } else { // 区间求和查询 int k, l, r; cin k l r; l ; int src roots[k 1]; cout query(src, 1, n, l, r, 1, 0) \n; roots[i] roots[i - 1]; } } return 0; }

【题解】可持久化区间仿射区间和（Persistent Range Affine Range Sum）

相关推荐

告别手速焦虑：5分钟掌握大麦抢票脚本终极指南

ProxySQL源码编译常见问题与解决方案

mcp-gsc安全最佳实践：保护你的GSC数据和API凭证

更多资讯

谁是省时神器？8款AI论文网站梯队榜，毕业季救星！

从合租分到退款清算：游戏租号平台分账系统的技术架构拆解

视频孪生+穿云透雾：单目视频三维实时重构驱动边防线全域四维态势感知与非法越境智能预警

AI资讯日报实战：从信息洪流到精选筛选的完整方法论

Keil5 RTE组件管理：STM32工程搭建高效指南

Octop自托管AI助手平台：多用户共享部署与配置实战

今日更新

济南做网站多少钱：3个案例拆解，防黑源码下载全攻略

婚恋网站实战案例：避开3个高价坑，省钱50%还能跑赢流量

制作网页比较方便的软件怎么选?一文搞懂避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？