P8512

P8512 直接做不好做，考虑离线。这个覆盖操作和这道题很像，可以直接对某些段暴力修改，可以直接上 ODT。发现当 ODT 执行这些操作时，是容易求出不执行某些操作后带来的值的影响的，即可以直接用树状数组维护每个位置现在是被那个操作覆盖，求出 \(1\) 到 \(x\) 操作还覆盖了那些位置，以及这 ......

题目传送门 先考虑没有区间限制怎么做，即执行完所有操作在询问全局和。用 \(set\) 维护连续段,就是珂朵莉树，写个模板即可。 加上区间限制呢？先将询问按照 \(r\) 排序。又因为还要维护每个 \(l\)，就在颜色段上在记录加入时间。我们在时间维开个数据结构，简单的树状数组即可。时间复杂度 \( ......

题外话 纪念一下第一道 Ynoi Easy Round.（上次那个是 Ynoi 模拟赛，什么时候才能做正统 Ynoi 啊/ll 在图老师的逼迫下换了洛谷博客的主题和背景，还挺好看的感觉。 原题传送门 题意 给定一个长度为 \(m\) 的序列，初始全为 \(0\)。再给 \(n\) 个区间赋值操作。 ......