1 条题解
-
0
题目分析
雨(rain)题解
卷王狂潮的过程其实构成了一棵满二叉树,LTF 只需要与 中的胜者竞争。有一个自然的贪心策略是在 LTF 参与的这 场竞争中,能不使用金手指就不使用,也就是说每次竞争如果不使用金手指就会被淘汰,那就使用金手指使得 LTF 的幸福指数与对手恰好相等,这样由于 LTF 编号最小,对手一定会被淘汰。假设知道了 区间内的胜者的幸福指数,那么模拟这个过程是 的。
于是考虑每次修改对于胜者的幸福指数的影响,不难发现第 和第 个人的幸福指数同时加上 相当于没加,所以区间修改顶多会在端点处会产生影响。维护一下树形结构,就可以 地处理出端点修改造成的变化。复杂度 。
- 1
信息
- ID
- 179
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者