当前位置: 首页 > news >正文

AT_iroha2019_day4_l 题解

题意:有一个数轴, \(Q\) 次操作,三种操作类型:

  • 1.在位置为 \(x\) 处插入权值为 \(w\) 的数,不会在有数的位置重复插入。
  • 2.删除位置 \(x\) 处的数,保证删前 \(x\) 处有数。
  • 3.给定位置 \(x\) ,对于一个数轴上有数的位置 \(y\) ,定义其价值为 \(\frac{w_y}{|y-x|}\) ,查询最大价值。

先假设没有修改操作。

对于一个查询 \(x\) ,我们可以分开处理小于 \(x\) 的位置和大于 \(x\) 的位置。不妨先考虑大于 \(x\) 的位置。把每一个数看作是二维平面上的一个点,一个点能成为哪些位置的最优选择?

如图,对应颜色的线条为该点所能影响的区域。我们可以维护一个凸包。

加上修改,可以考虑线段树分治,对于操作时间建立线段树,统计每一个修改和查询对应的时刻区间。对于每个线段树上的节点维护一个凸包,本题求的是区间max,两个时间区间的答案可以直接合并。

按在数轴上的位置将插入和查询从右到左排序,依次在线段树上插入和查询。

对于在查询左边的情况也是类似的

http://www.hskmm.com/?act=detail&tid=21100

相关文章:

  • AT_abc290_f 题解
  • 一张图读懂绿电直连系统架构 - 智慧园区
  • P5469 [NOI2019] 机器人 题解
  • 题解:P14080 [GESP202509 八级] 最小生成树
  • 实用指南:Spring Cloud Gateway 实战:全局过滤器日志统计与 Prometheus + Grafana 接口耗时监控
  • GTSAM 中自定义因子(Custom Factor)的详解和实战示例 - 指南
  • AtCoder AGC073 A 题解
  • CF506C Mr. Kitayuta vs. Bamboos 51nod1457 小K vs. 竹子 题目分析
  • 北京 意大利 硕士学签/D签 vfs代办 材料清单
  • temp
  • 我有园子了
  • 使用 Jenkins 的流水线方案实施 CI/CD
  • 加密的病例单
  • 详细介绍:视频融合平台EasyCVR构筑智慧交通可视化管理与智能决策中枢
  • docker 在x86上build arm 镜像
  • 9.29软工
  • 不一样的.NET烟火,基于Roslyn的开源代码生成器
  • 复刻江协旋钮控制模块
  • 告别硬编码!5个让Web自动化脚本更稳定的定位策略
  • 从零开始,使用Idea工具搭建一个springboot项目
  • 最优/极值问题的算法选择
  • 第三方控件库的添加和使用
  • C4NR PVP服务器1.2 天穹炮塔更新
  • 树形dp [JOI Open 2020] 发电站 / Power Plant
  • 深入解析:灵画-AI绘画小程序
  • AT_arc156_b [ARC156B] Mex on Blackboard
  • 产品排序
  • 环形链表II-leetcode
  • ubuntu20.04安装nvidia显卡
  • [线段树系列 #6] 标记永久化