明天周日，能晚起床了??????！
上午打学车的那个公开赛，T1 不会，haosen 说了个 \(O(\frac{n^4}{w})\) 的做法，但是我不会，也懒得写了。T2 五分钟出正解，调半个小时。T3T4 看部分分太杂且分数不高就不想打了。最终没加 freopen，喜提 \(0pts\)???
下午改题改不动，摆了，晚上还有 ABC，R 竟然不让隔壁去打了，妈的???，没法让隔壁带着上分了???
中午被 haosen 和 lyt 和 sbf 学长 D 说闲话太没意思了???，但是也没啥可写的啊???，让我写 sbf 学长和 lyt 的爱情故事吗/yiw，他俩在一起的时候我也没在旁边啊???。
下午觉得总是听自己的那个歌单太单调了，就开始随机播放 arcaea 电台了。哦哦哦上午学车那个还是 arcaea 场啊，题都是红和白姬的剧情，但是我没买白姬包，怎么会是呢???。没钱了???。
考完 csp 他们好像要出去玩一晚上，但是我不太想出去玩（。打算让家长最近几天把我板子寄过来然后到时候去那玩去（。
想知道 HZOI 那边有多少打音游的/yiw???
好久没打音游了，别在秦皇岛一打直接开始 -0.01???，现在断网的操作都不熟练了妈的，上次放假的时候一断网按成打开引导式访问了，妈的。
晚上辉针城混关成功！最后还剩俩残，真的好爽（），「Blue Lady Show」好好听???
今天戴老师往群里发本子了/se/se/se，但是还没开始看???
”种族歧视“用文言文来讲是不是就是”以色列人“。
推歌：next to you -uma feat.橘花音
幻听：永夜抄三面道中
P3688
我们转化完题意就能发现，我们要求的其实就是 \(a_{l-1}=a_r\) 的概率。我们设 \(p_{x, y}\) 为 \(a_x=a_y\) 的概率，进行一个分类讨论。
- 当 \(x<l,l\le y\le r\) 时，\(a_x\) 和 \(a_y\) 相同情况变化的概率为 \(\frac{1}{r-l+1}\)。
- 当 \(l\le x\le r, r<y\) 时，变化的概率为 \(\frac{1}{r-l+1}\)。
- 当 \(l\le x<y\le r\) 时，变化的概率为 \(\frac{2}{r-l+1}\)。
- 这里还有一个特殊情况为 \(l=1\) 时，这次这一次询问答案不变就等价于 \(sum_{1\sim r}=sum_{r\sim n}\)。那么再对这种情况分类讨论：
- 当 \(x=1, l\le y\le r\) 时，变化的概率为 \(\frac{r-l}{r-l+1}\)。
- 当 \(y<l\) 或 \(y>r\) 时，变化的概率是 \(1\)。
于是我们可以用树套树来维护。设当前操作不变的概率为 \(q\)，原先相等的概率为 \(p\)，那么新的相等的概率为 \(pq+(1-p)(1-q)\)。树套树标记永久化一下即可。
时间复杂度 \(O(n\log ^2n)\)。
为什么全世界就我不会标记永久化啊
