acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(0)讨论(0)提交记录(0)
  • 并查集 + 离线 ( O(n) 做法 )

    离线 + 并查集 * 因为后面的 染色 优先级更大,所以将 染色 操作 存起来,然后 倒序 处理。(离线操作) * 那么对于后来的染色[L,R], 如果前面的染色已经包含了[L,R],则丢弃,否则要找出[L,R]中未被染色的区间。 * 用并查集 fa[i] 表示 i 位置左边最近未染色的位置是哪里,对于 find(R) < L的 染色 直接丢弃(已经被包含) , 否则 染色 find(R) ,同时令 fa[find(R)] = find(L-1) (表示染色到 L ) , 然后 沿着 find(R)-1走上述过程就行了。 可以证明,每个点只会被染色一次,所以时间复杂度是 O(n)

    userId_undefined

    深圳福田CBD黄老师

    倔强青铜
    132阅读
    1回复
    1点赞
  • A5903.涂色 题解

    userId_undefined

    知予

    倔强青铜
    57阅读
    1回复
    0点赞
  • 题解

    都有区间推平了怎么没有ODT呢 Code:

    userId_undefined

    亚洲卷王 AK IOI

    尊贵铂金
    5阅读
    2回复
    0点赞
首页