- 主题:求动态区间k大 (转载)
哪有你这样算的
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 不行，需要各种操作都是O(logn*logn)
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
当然有的，我的要求都是低的，论文中能做到的更牛逼。你先可以查查带修改区间k大数相关的论文。
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 不行，需要各种操作都是O(logn*logn)
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
你这种做法有问题，k可以是任意值。看=O(n).不能假定很小
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 不行，需要各种操作都是O(logn*logn)
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
选择集可以很大，甚至是全集，也必须要满足我说的复杂度
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 不行，需要各种操作都是O(logn*logn)
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
你可以有预处理，预处理时间允许为O(nlogn*logn)
【 在 hongdiao 的大作中提到: 】
: 【 在 ylh1969 的大作中提到: 】
: : 你的问题是有序问题，躲不开排序技术。
: : 你需要寻找满足O(logn*logn)的排序技术。
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 223.104.212.*
没多打，就是这样的，你预处理少了后面就很难支持修改
【 在 hongdiao 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 你可以有预处理，预处理时间允许为O(nlogn*logn)
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 115.238.195.*
这是算法题，okay？
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 你这种做法有问题，k可以是任意值。看=O(n).不能假定很小
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 115.238.195.*
是，我没说不允许你用更少的预处理时间，你只要能支持后续单次操作时间复杂度为o(logn*logn)
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 这是算法题，okay？
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 220.178.225.*
当然不是open problem？
【 在 here080 的大作中提到: 】
: 你才搞笑，是你自己没表达清楚。所有人都理解成我理解的意思了。
: 即使在这一贴，你的表达也很堪忧。
:
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 205.185.123.*
给你一篇论文，人家做到的比我的要求还要好，空间与时间都更省一个loglogn
https://link.springer.com/chapter/10.1007%2F978-3-642-10631-6_83。
Our dynamic data structure uses O(nlogn/loglogn) space and supports queries and updates in O((logn/loglogn)^2) time.
【 在 here080 的大作中提到: 】
: 你才搞笑，是你自己没表达清楚。所有人都理解成我理解的意思了。
: 即使在这一贴，你的表达也很堪忧。
:
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 205.185.123.*