這篇題解是和群友對(duì)線產(chǎn)物

題目描述可以去https://www.cspro.org/ 點(diǎn)模擬考試->登錄->模擬考試->試題編號(hào)202109-5去看。實(shí)在是太長(zhǎng)了（

讀這題和寫這題的過(guò)程深刻讓我體會(huì)到了把中文題讀對(duì)有多么難

依賴題目：

• P3690 【模板】動(dòng)態(tài)樹(shù)（Link Cut Tree）https://www.luogu.com.cn/problem/P3690

• P1501?[國(guó)家集訓(xùn)隊(duì)]Tree II?https://www.luogu.com.cn/problem/P1501

• P3919?【模板】可持久化線段樹(shù) 1（可持久化數(shù)組）?https://www.luogu.com.cn/problem/P3919
  

大意：您需要寫一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持以下四種強(qiáng)制在線的操作：

1、向數(shù)列末尾插入一個(gè)元素

2、數(shù)列末尾彈出一個(gè)元素

3、若一個(gè)元素在先前第s次操作產(chǎn)生的數(shù)列中的區(qū)間[l, r]內(nèi)，將其乘上一個(gè)數(shù)y

4、對(duì)于先前第s次操作產(chǎn)生的數(shù)列，查詢區(qū)間[l, r]中的每個(gè)元素修改后最終版本的總和

答案對(duì)一個(gè)給定的不超過(guò)int表示范圍數(shù)取模。

坑點(diǎn)：

1、我們不關(guān)心每個(gè)元素歷史版本的值如何，只關(guān)心最終的值。

2、讀樣例解釋，如果代入主席樹(shù)的思路發(fā)現(xiàn)3操作會(huì)影響涉及的元素當(dāng)前及之后的所有版本的值，也就是得在時(shí)間上再維護(hù)這些區(qū)間，不太可做。

3、被刪除的元素也不能忽略，它可能會(huì)被3操作修改，被4操作查詢。

于是第一眼是主席樹(shù)板題（我口胡的），動(dòng)手寫起來(lái)發(fā)現(xiàn)假之又假……

換個(gè)思路，既然不能把一個(gè)元素真正刪除掉，那么我們就干脆維護(hù)一個(gè)分支，將刪除操作變?yōu)樘缴弦粋€(gè)節(jié)點(diǎn)，插入元素變?yōu)樵诋?dāng)前節(jié)點(diǎn)連入一個(gè)新節(jié)點(diǎn)，并把當(dāng)前節(jié)點(diǎn)設(shè)為這個(gè)新節(jié)點(diǎn)。

涂了一下發(fā)現(xiàn)這樣弄出來(lái)是一棵樹(shù)，那么3操作就變成樹(shù)上的一條路徑上的乘法。把樹(shù)映射成序列（輕重鏈剖分）可以很方便的建樹(shù)然后做乘法，但是強(qiáng)制在線要求動(dòng)態(tài)連邊，于是考慮LCT。LCT可以輕易做到路徑乘法，動(dòng)態(tài)連邊或刪邊。那么只需要用一棵主席樹(shù)維護(hù)一下可持久化數(shù)組就可以算出詢問(wèn)的[l, r]的兩個(gè)端點(diǎn)到底是樹(shù)上哪兩個(gè)點(diǎn)，于是這題就做完了。

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