c******n
发帖数: 4965 | 1 http://www.lintcode.com/en/problem/count-of-smaller-number/#
用segment tree 怎么解？
我只能想到分割值域空间 0----K
time is O(NlogK)， can't do O(NlogN), and won't work if we have infinite
value range
难度写成是medium, 好像有些难。 |
c******n
发帖数: 4965 | 2 re
【在 c******n 的大作中提到】
: http://www.lintcode.com/en/problem/count-of-smaller-number/#
: 用segment tree 怎么解？
: 我只能想到分割值域空间 0----K
: time is O(NlogK)， can't do O(NlogN), and won't work if we have infinite
: value range
: 难度写成是medium, 好像有些难。
|
x*******9
发帖数: 138 | |
c******n
发帖数: 4965 | 4 bit 就是 segment tree, 这个我已经说了， 问题是怎么应对infinitely large
values
【在 x*******9 的大作中提到】
: Binary Indexed Tree
|
c******n
发帖数: 4965 | 5 刚看了bit tree 基本跟segment tree 差不多，
但是bit tree 必须只能算 additive statistics. such as sum., 这个题目要count
小于某个值的个数， 看不出来怎么套用
【在 x*******9 的大作中提到】
: Binary Indexed Tree
|
c******n
发帖数: 4965 | 6 找到了 http://pavelsimo.blogspot.com/2012/09/counting-inversions-in-array-using-BIT.html
有点绕， 看明白了还是很简单的。。。。
count
【在 c******n 的大作中提到】
: 刚看了bit tree 基本跟segment tree 差不多，
: 但是bit tree 必须只能算 additive statistics. such as sum., 这个题目要count
: 小于某个值的个数， 看不出来怎么套用
|
x*******9
发帖数: 138 | 7 http://lpaste.net/132699
要区分在线算法和离线算法。。。
当然，离线算法基本就是上帝模式开挂。。。 |
