1 条题解

  • 0
    @ 2022-8-8 15:09:06

    这个是个裸的区间染色段数均摊 考虑维护每个点与其颜色相同的前驱 用平衡树维护颜色连续段,然后考虑一个颜色连续段里面除了第一个点以外,后面的点i的前驱都是i-1 用树套树/分治维护,于是这个颜色段的变化可以O( log^2n )维护 总复杂度O( (n+m)log^2n )

    注意常数… 小心细节…

    • 1

    信息

    ID
    3640
    时间
    1500ms
    内存
    64MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者