最大k, [0] & lt; [k], [1] & lt; [k + 1], . .， A[k-1]

Question

我需要这个问题的有效算法(时间复杂度小于O(n^2))，请帮助我:

[我. .[J]被称为[i]…j] & lt;b我. .如果a[i]<b[i]，>给定数组A[1..]N]， (N <= 10^5, a[i]<= 1000)。求A[1..]k] & lt;(k + 1 . . 2 k)

例如，n=10: 2 2 1 4 3 2 5 4 2 3答案是4

很容易看出k <= n/2。所以我们可以使用蛮力(k从n/2到1)，但不能使用二进制搜索。

我不知道该怎么处理[I] <= 1000。也许用地图??

Answer 1

使用范围更新的Fenwick树。树中的每个索引表示窗口A中比它小的数的计数。为了使窗口有效，B(右侧窗口)中的每个元素必须在A(左侧窗口)中有一个伙伴。当我们将数字x移到a中时，我们将1添加到范围中，在树中添加[x+1, 1000]。对于从B移动到A的元素，在其树索引中添加1。对于B中的每个新元素，将-1添加到树中的索引中。

如果索引低于0，则该窗口无效。在这个例子中，我们有:

2 2 1 4 3 2 5 4 2 3
2 2
|
Tree:
add 1 to [3, 1000]
add -1 to 2
idx  1  2  3  4  5
val  0 -1  1  1  1 (invalid)

2 2 1 4 3 2 5 4 2 3
2 2 1 4
|
Tree:
add 1 to [3, 1000]
add 1 to 2 (remove 2 from B)
add -1 to 1
add -1 to 4
idx  1  2  3  4  5
val -1  0  2  1  2 (invalid)

2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2
|
Tree:
add 1 to [2, 1000]
add 1 to 1 (remove 1 from B)
add -1 to 3
add -1 to 2
idx  1  2  3  4  5
val  0  0  2  2  3 (valid)

2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4
|
Tree:
add 1 to [5, 1000]
add 1 to 4 (remove 4 from B)
add -1 to 5
add -1 to 4
idx  1  2  3  4  5
val  0  0  2  2  3 (valid)

2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4 2 3
|
Tree:
add 1 to [4, 1000]
add 1 to 3 (remove 3 from B)
add -1 to 2
add -1 to 3
idx  1  2  3  4  5
val  0 -1  2  3  4 (invalid)