专栏文章

AT_iroha2019_day4_l 题解

PPenguinJ
AT_iroha2019_day4_l题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio8r02w
此快照首次捕获于
2025/12/02 15:12
3 个月前
此快照最后确认于
2025/12/02 15:12
3 个月前
查看原文
题意：有一个数轴， QQ 次操作，三种操作类型：
  • 1.在位置为 xx 处插入权值为 ww 的数，不会在有数的位置重复插入。
  • 2.删除位置 xx 处的数，保证删前 xx 处有数。
  • 3.给定位置 xx ，对于一个数轴上有数的位置 yy ,定义其价值为 wy∣y−x∣\frac{w_y}{|y-x|} ，查询最大价值。
先假设没有修改操作。
对于一个查询 xx ，我们可以分开处理小于 xx 的位置和大于 xx 的位置。不妨先考虑大于 xx 的位置。把每一个数看作是二维平面上的一个点，一个点能成为哪些位置的最优选择？
如图，对应颜色的线条为该点所能影响的区域。我们可以维护一个凸包。
加上修改，可以考虑线段树分治，对于操作时间建立线段树，统计每一个修改和查询对应的时刻区间。对于每个线段树上的节点维护一个凸包，本题求的是区间max，两个时间区间的答案可以直接合并。
按在数轴上的位置将插入和查询从右到左排序，依次在线段树上插入和查询。
对于在查询左边的情况也是类似的

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...