CCF CSP 2021-09 T5 箱根山岳险天下（LCT+主席树）

这篇题解是和群友对线产物

题目描述可以去https://www.cspro.org/ 点模拟考试->登录->模拟考试->试题编号202109-5去看。实在是太长了（

读这题和写这题的过程深刻让我体会到了把中文题读对有多么难

依赖题目：

• P3690 【模板】动态树（Link Cut Tree）https://www.luogu.com.cn/problem/P3690

• P1501 [国家集训队]Tree II https://www.luogu.com.cn/problem/P1501

• P3919 【模板】可持久化线段树 1（可持久化数组） https://www.luogu.com.cn/problem/P3919
  

大意：您需要写一个数据结构，支持以下四种强制在线的操作：

1、向数列末尾插入一个元素

2、数列末尾弹出一个元素

3、若一个元素在先前第s次操作产生的数列中的区间[l, r]内，将其乘上一个数y

4、对于先前第s次操作产生的数列，查询区间[l, r]中的每个元素修改后最终版本的总和

答案对一个给定的不超过int表示范围数取模。

坑点：

1、我们不关心每个元素历史版本的值如何，只关心最终的值。

2、读样例解释，如果代入主席树的思路发现3操作会影响涉及的元素当前及之后的所有版本的值，也就是得在时间上再维护这些区间，不太可做。

3、被删除的元素也不能忽略，它可能会被3操作修改，被4操作查询。

于是第一眼是主席树板题（我口胡的），动手写起来发现假之又假……

换个思路，既然不能把一个元素真正删除掉，那么我们就干脆维护一个分支，将删除操作变为跳到上一个节点，插入元素变为在当前节点连入一个新节点，并把当前节点设为这个新节点。

涂了一下发现这样弄出来是一棵树，那么3操作就变成树上的一条路径上的乘法。把树映射成序列（轻重链剖分）可以很方便的建树然后做乘法，但是强制在线要求动态连边，于是考虑LCT。LCT可以轻易做到路径乘法，动态连边或删边。那么只需要用一棵主席树维护一下可持久化数组就可以算出询问的[l, r]的两个端点到底是树上哪两个点，于是这题就做完了。

https://paste.ubuntu.com/p/8GyXK4KNtk/

造的板子很多参考了FlashHu和yyb的代码，这里贴出博客链接：

https://www.cnblogs.com/flashhu/p/8324551.html

https://www.luogu.com.cn/blog/cjyyb/solution-p3391