【OI笔记】2021.8.12

Day4

¶上午

今天自习，看看某神仙的言论：（好叭我不是神仙我先GUN了）上午一直在啃昨天的T1，本来想用dsu on tree的，看到using大V已经实现，就试了试，结果还是败在了昨天的那个地方。所以还是采取了题解的思路：平衡树。。平衡树这里有几个坑，一是不能越界，比如说这里：

if(j+len[x]+1>=L[x]&&j+1<=R[x])
{
    ans[x]=max(ans[x],query(1,dfn[x]+max(0ll,L[x]-j-1);
    dfn[x]+min(len[x],R[x]-j-1))+pl);
}

还有就是些七七八八的小细节想想都头痛。。。线段树这里还好，是一颗灰常标准的线段树。打代码的时间不长，主要是手贱，所以debug的时间占了大半部分，经常出现这种情况到头来一看：

哦，dfs根本没有出来

还会犯一些知识性的错误，比如说前几天的运算符优先问题，这种问题倒是要现在多犯，考试别犯。还是要唯手熟尔才行啊。

¶下午

下午复习了一下莫队，做了几道题。到头来我树上莫队还是搞得模模糊糊的，SP10707也是摸着石头过河。（只配做普通膜对）。下午这道题P5268 SNOI2017一个简单的询问是一道很明显的区间多组离线询问题，所以肯定要用莫队来做（为什么“肯”是前鼻音！！！），但是题目要求的东西着实有些感人再看，我们可以用差分（Excel里边早就说过了我还以为是莫队差分二选一所以就毫不犹豫选了莫队，折腾了半个小时）。把柿子化简一下，就可以开工了。由于从不压行，硬是干到了90行。。啊，树上莫队我晚上搞，有欧拉两个字的这个真的不是什么好玩的东西接着，是期望概率DP。这一块不是很熟，所以我还是瞥了一眼题解，发现这个东西：