最大 k 使得 A[0]<A[k], A[1]<A[k+1], ..., A[k-1]<A[2*k-1],在对每个 k 排序之后-大小 window

Maximum k such that A[0]<A[k], A[1]<A[k+1], ..., A[k-1]<A[2*k-1], after sorting each k-sized window

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

a[i..j] is called a[i..j] < b[i..j] if a[i]<b[i], a[i+1]<b[i+1], ..., a[j]<b[j] after sorting these 2 arrays.
Given array A[1..n], (n<= 10^5, a[i]<= 1000). Find the maximum of k that A[1..k] < A[k+1..2k]

For example, n=10: 2 2 1 4 3 2 5 4 2 3 the answer is 4

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

而且我不知道如何处理 a[i] <= 1000。也许使用地图???

使用范围更新的分域树。树中的每个索引表示 window A 中有多少个数字小于它。要使 windows 有效,B(右边的 window)中的每个元素必须在 A(左边的 window)中有一个伙伴).当我们将数字 x 移到 A 中时,我们将 1 添加到树中的范围 [x+1, 1000] 中。对于从 B 移动到 A 的元素,在其树索引中添加 1。对于 B 中的每个新元素,将 -1 添加到它在树中的索引中。如果索引低于零,则 window 无效。

例如,我们有:

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)