P8512
P8512 [Ynoi Easy Round 2021] TEST_152 题解
P8512 直接做不好做,考虑离线。这个覆盖操作和这道题很像,可以直接对某些段暴力修改,可以直接上 ODT。发现当 ODT 执行这些操作时,是容易求出不执行某些操作后带来的值的影响的,即可以直接用树状数组维护每个位置现在是被那个操作覆盖,求出 \(1\) 到 \(x\) 操作还覆盖了那些位置,以及这 ......
P8512 [Ynoi Easy Round 2021] TEST_152
题目传送门 先考虑没有区间限制怎么做,即执行完所有操作在询问全局和。用 \(set\) 维护连续段,就是珂朵莉树,写个模板即可。 加上区间限制呢?先将询问按照 \(r\) 排序。又因为还要维护每个 \(l\),就在颜色段上在记录加入时间。我们在时间维开个数据结构,简单的树状数组即可。时间复杂度 \( ......