1 条题解

  • 0
    @ 2026-11-15 19:27:39

    题目分析

    雨(rain)题解

    卷王狂潮的过程其实构成了一棵满二叉树,LTF 只需要与 [2,2],[3,4],[5,8],⋯ ,[2n−1+1,2n][2,2],[3,4],[5,8],\cdots,[2^{n-1}+1,2^n] 中的胜者竞争。有一个自然的贪心策略是在 LTF 参与的这 nn 场竞争中,能不使用金手指就不使用,也就是说每次竞争如果不使用金手指就会被淘汰,那就使用金手指使得 LTF 的幸福指数与对手恰好相等,这样由于 LTF 编号最小,对手一定会被淘汰。假设知道了 [2w−1+1,2w][2^{w-1}+1,2^w] 区间内的胜者的幸福指数,那么模拟这个过程是 O(n)O(n) 的。

    于是考虑每次修改对于胜者的幸福指数的影响,不难发现第 2i−12i-1 和第 2i2i 个人的幸福指数同时加上 xix_i 相当于没加,所以区间修改顶多会在端点处会产生影响。维护一下树形结构,就可以 O(n)O(n) 地处理出端点修改造成的变化。复杂度 O(2n+nm)O(2^n+nm)。

    • 1

    信息

    ID
    179
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者