P5055 【模板】可持久化文藝平衡樹

突然發(fā)現(xiàn)fhq_treap也是可以支持區(qū)間翻轉的，所以基本上和其他平衡樹是一樣的，而且還滿足重量平衡樹的性質，真是太優(yōu)秀了，只不過常數(shù)稍微比較大。

然后這里我們變成了一顆區(qū)間平衡樹，需要支持以下幾個操作。
若 opti=1，則接下來兩個整數(shù) pi,xi?，表示操作為在第 pi個數(shù)后插入數(shù) x。
若 opti=2，則接下來一個整數(shù) pi?，表示操作為刪除第 pi個數(shù)。
若 opti=3，則接下來兩個整數(shù) li,ri，表示操作為翻轉區(qū)間 [li,ri]。
若 opti=4，則接下來兩個整數(shù) li,ri?，表示操作為查詢區(qū)間 [li,ri]的和。

插入刪除就直接split和merge，翻轉區(qū)間就是打標記，相當于對整個子樹的左右兒子翻轉。

總結

以上是生活随笔為你收集整理的P5055 【模板】可持久化文艺平衡树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。