- 主题:求动态区间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.*
感觉像BIT 结构
【 在 Analog 的大作中提到: 】
: 发信人: Analog (模拟人生), 信区: Algorithm
: 标 题: 求动态区间k大
: 发信站: 水木社区 (Mon Jun 8 20:00:30 2020), 站内
: ...................
--
FROM 67.163.48.*
直接一棵树不行吗？
【 在 Analog (模拟人生) 的大作中提到: 】
: 标 题: 求动态区间k大
: 发信站: 水木社区 (Mon Jun 8 20:03:21 2020), 站内
:
: 【 以下文字转载自 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.*]
--
FROM 76.126.252.*
怎么搞
【 在 here080 的大作中提到: 】
: 直接一棵树不行吗？
: 【 在 Analog (模拟人生) 的大作中提到: 】
: : 标 题: 求动态区间k大
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
一个排序二叉树就基本符合要求了。
再在每个结点存上统计信息，即该结点左边和右边的子结点数，这就成了一个“统计二叉树”。这不就可以满足要求了？
【 在 Analog (模拟人生) 的大作中提到: 】
: 标 题: Re: 求动态区间k大 (转载)
: 发信站: 水木社区 (Wed Jun 10 07:13:34 2020), 站内
:
: 怎么搞
: 【 在 here080 的大作中提到: 】
: : 直接一棵树不行吗？
: : 【 在 Analog (模拟人生) 的大作中提到: 】
: : : 标 题: 求动态区间k大
: : ....................
:
: - 来自「最水木 for iPhone 6s」
: --
:
: ※ 来源:·最水木 客户端·[FROM: 223.104.212.*]
--
FROM 76.126.252.*
不行吧，现在让你求的是区间第k大，比如10个数，每次给你一个区间比如3，7，求这个区间内第二大的数据
【 在 here080 的大作中提到: 】
: 一个排序二叉树就基本符合要求了。
: 再在每个结点存上统计信息，即该结点左边和右边的子结点数，这就成了一个“统计二叉树”。这不就可以满足要求了？
: 【 在 Analog (模拟人生) 的大作中提到: 】
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
【 在 Analog (模拟人生) 的大作中提到: 】
: 不行吧，现在让你求的是区间第k大，比如10个数，每次给你一个区间比如3，7，求这个区间内第二大的数据
: - 来自「最水木 for iPhone 6s」
堆排序的堆？
--
FROM 106.121.160.*
可以先查出3或者7对应的排序，然后区间内的统计就变成全局统计了。
【 在 Analog (模拟人生) 的大作中提到: 】
: 标 题: Re: 求动态区间k大 (转载)
: 发信站: 水木社区 (Wed Jun 10 07:34:38 2020), 站内
:
: 不行吧，现在让你求的是区间第k大，比如10个数，每次给你一个区间比如3，7，求这个区间内第二大的数据
: 【 在 here080 的大作中提到: 】
: : 一个排序二叉树就基本符合要求了。
: : 再在每个结点存上统计信息，即该结点左边和右边的子结点数，这就成了一个“统计二叉树”。这不就可以满足要求了？
: : 【 在 Analog (模拟人生) 的大作中提到: 】
: : ....................
:
: - 来自「最水木 for iPhone 6s」
: --
:
: ※ 来源:·最水木 客户端·[FROM: 223.104.212.*]
--
FROM 76.126.252.*
问题每次区间范围都会变的啊，而且存在修改操作，要不你再考虑一下吧
【 在 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.*