- 主题:求动态区间k大 (转载)
【 以下文字转载自 Algorithm 讨论区 】
发信人: Analog (模拟人生), 信区: Algorithm
标 题: 求动态区间k大
发信站: 水木社区 (Mon Jun 8 20:00:30 2020), 站内
给定一个序列a1...an，值域范围为64位整数，然后m次操作，其中有一些为单点修改操作，一些为询问操作，要求空间为O（nlogn），每次操作复杂度不超过0（logn*logn）。强制在线。怎么做？
- 来自「最水木 for iPhone 6s」
--
FROM 117.136.8.*
怎么搞
【 在 here080 的大作中提到: 】
: 直接一棵树不行吗？
: 【 在 Analog (模拟人生) 的大作中提到: 】
: : 标 题: 求动态区间k大
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
不行吧，现在让你求的是区间第k大，比如10个数，每次给你一个区间比如3，7，求这个区间内第二大的数据
【 在 here080 的大作中提到: 】
: 一个排序二叉树就基本符合要求了。
: 再在每个结点存上统计信息，即该结点左边和右边的子结点数，这就成了一个“统计二叉树”。这不就可以满足要求了？
: 【 在 Analog (模拟人生) 的大作中提到: 】
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
问题每次区间范围都会变的啊，而且存在修改操作，要不你再考虑一下吧
【 在 here080 的大作中提到: 】
: 可以先查出3或者7对应的排序，然后区间内的统计就变成全局统计了。
: 【 在 Analog (模拟人生) 的大作中提到: 】
: : 标 题: Re: 求动态区间k大 (转载)
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
当然不是堆
【 在 billybear04 的大作中提到: 】
: 【 在 Analog (模拟人生) 的大作中提到: 】
: : 不行吧，现在让你求的是区间第k大，比如10个数，每次给你一个区间比如3，7，求这个区间内第二大的数据
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
你搞笑吧，比如初始化10个数
3 2 5 7 6 4 1 9 8 10
第一次查询 3 7 2 应该返回4
第二次为修改 5 8，此时序列变成3 2 5 7 8 4 1 9 8 10
第三次为查询 4 9 3，此时应该返回7
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 不行吧，现在让你求的是区间第k大，比如10个数，每次给你一个区间比如3，7，求这个区间内第二大的数据
:
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 180.164.182.*
老兄，给的是区间的位置啊
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 你搞笑吧，比如初始化10个数
: : 3 2 5 7 6 4 1 9 8 10
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 180.164.182.*
你的时间复杂度还有保证吗？
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 老兄，给的是区间的位置啊
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 180.164.182.*
不行，需要各种操作都是O(logn*logn)
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 你的时间复杂度还有保证吗？
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 180.164.182.*
是啊
【 在 officercat 的大作中提到: 】
: 啥叫区间k大？区间是说给定数组下标的范围？
:
: 【 在 Analog 的大作中提到: 】
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*