2024.8.13
洛谷P2391 白雪皑皑
并查集维护序列连通性的一道好题。
倒序操作，用并查集维护下一个未被染色的位置来染色。
洛谷P3295 [SCOI2016] 萌萌哒
并查集维护区间相等的限制
使用类似ST表的结构，同一层内建并查集，把一段区间限制拆成log段限制直接维护
下传时将本节点的左右儿子分别和本层并查集上自己的根节点的左右儿子在下一层的并查集里面直接合并
最后下传至最下面统计答案
2024.8.14
洛谷P2221 [HAOI2012] 高速公路
线段树根据询问的式子维护需要的信息
洛谷P6619 [省选联考 2020 A/B 卷] 冰火战士
树状数组上二分经典题
维护两个序列A、B，要找一个分界点，满足A的前缀和和B的后缀和的最小值最大
发现把两个序列的前缀和/后缀和画出来，则A的前缀和递增，B的后缀和递减，答案就在交点附近
树状数组维护两个序列，A直接维护，B记一下总和，再把错开一位的前缀和减去总和，实现两个序列下标的对齐
查询时从头开始，每次在树状数组上往前跳 \(2^k\) 步，k递减，每一次检查跳的下一位两个序列的大小关系，判断是否越过交点，最终找到交点
复杂度 \(O(Q \log Q)\)，树状数组小常数可过
要注意最优解不一定在交点上，可能在附近，最大能量值不在交点就在交点+1，但是可能更高的温度也对应相同的答案，要多扫一次