首页 > 其他 > 详细

Aizu 3118 Range Min of Max Query

时间:2020-05-05 23:35:51      阅读:122      评论:0      收藏:0      [点我收藏+]

URL

https://onlinejudge.u-aizu.ac.jp/problems/3118

解法

定期重构,假设每块的大小是 \(S\)

  • 块内询问只有 \(O(S)\) 个不同的端点
  • 对相邻端点间建一个支持快速查询的数据结构(按照 \(B_i-A_i\) 排序,算前后缀最小值)
  • 暴力更新

复杂度 \(O(N \sqrt{Q} \log{N})\)

实现

https://ideone.com/REiwCW

Aizu 3118 Range Min of Max Query

原文:https://www.cnblogs.com/iefnah06/p/12832927.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!