[CF896C]Willem, Chtholly and Seniorious[ODT]

为了更好的骗分完成CF558E A Simple TaskCF896C Willem, Chtholly and Seniorious, 特意学了这种新的毒瘤数据结构.

ODT的思想很好理解, 就是把一段值相同的区间压缩为1个节点, 即每个节点记录一个三元组$latex (l,r,v)$, 表示区间$latex [l,r]=v$. 然后把这些节点以l为关键字都丢到set里面, 每当要进行区间操作时, 以待操作区间左右端点为界把分界点所在区间拆开, 暴力操作. 但如果仅仅这样节点越拆越多, 每个节点代表的区间长度短, 时间复杂度会严重退化. 降低时间复杂度的关键操作是区间赋值, 这个操作直接把一个区间内的多个节点合并为1个, 在数据随机时复杂度趋近于$latex O(N\log N)$. 但如果区间赋值操作少的话就会被卡成暴力了.

注意区间幂次和那里的快速幂底数一开始就要取一次mod, 否则会爆longlong导致第四个点WA. 几个要注意的细节见代码注释.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址