0

我试图使用 Fenwick 树数据结构解决关于 codeforces 的多集问题（ https://codeforces.com/contest/1354/problem/D ）。我通过了示例测试用例，但提交后出现内存限制错误，测试用例如下所述。（基本上测试用例是：

1000000 1000000

1.............1 //10^6 次

-1...........-1 //10^6 次）。

我在我的 IDE 中尝试了类似的测试用例并得到了下面提到的错误。（与上面类似，我提供的测试用例是：

1000000 1

1.............1 //10^6 次

-1

)

线程“主”java.lang.IndexOutOfBoundsException 中的异常：索引 524289 超出 java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64) 处 java.base/jdk.internal 的长度 524289 的范围。 util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70) 在 java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248) 在 java.base/java.util.Objects.checkIndex(Objects.java: 373) 在 java.base/java.util.ArrayList.get(ArrayList.java:426) 在 MultisetKt.main(multiset.kt:47) 在 MultisetKt.main(multiset.kt)

这是我的代码：

private fun readInt() = readLine()!!.split(" ").map { it.toInt() }

fun main() {
    var (n, q) = readInt()
    var list = readInt() //modify the list to store it from index 1
    var finalList = listOf(0) + list
    val query = readInt()
    var bit  = MutableList(n+1){0}

    fun update(i:Int, value:Int) {
        var index = i
        while(index < n){
            bit.set (index , bit[index] + value)
            index += (index and -index)
        }
    }
    fun rangefunc(i:Int): Int {
        var su = 0
        var index = i
        while(index > 0){
            su += bit[index]
            index -= (index and -index)
        }
        return su
    }
    fun find(x:Int):Int {
        var l = 1
        var r = n
        var ans = n
        var mid = 0
        while (l <= r) {
            mid = (l + r) / 2
            if (rangefunc(mid) >= x) {
                ans = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return ans
    }
    for (i in 1..n) {
        update(finalList[i], 1)
    }
    for (j in 0..q - 1) {
        if (query[j] > 0) {
            update(query[j], 1)
        } else {
            update(find(-query[j]), -1)
        }
    }
    if(rangefunc(n) == 0){
        println(0)
    }else{
        println(find(1))
    }
}

我相信这是因为 BITlist 无法存储 10^6 个元素但不确定。请让我知道我应该对我的代码进行哪些更改，以及有关将来如何处理此类情况的任何其他建议。

先感谢您 ：）

4

1 回答 1

3

一个 ArrayList 可以存储超过 20 亿个项目 (2 * 10^9)。那不是你的问题。ArrayIndexOutOfBoundsException 用于尝试访问小于零或大于或等于其大小的 ArrayList 的索引。换句话说，它还没有包含的索引。

那里的代码比我调试的时间多。但我将从堆栈跟踪指向的行开始，看看您如何尝试bit[index]使用等于 ArrayList 大小的索引进行调用。

要回答您的字面问题，您可以明确使用 LinkedList 作为您的 MutableList 类型以避免大小限制，但它更重并且在按索引访问元素时更慢。

于 2020-07-14T13:11:59.223 回答