0

フェンウィック ツリー データ構造を使用して、コードフォースに関するマルチセットの質問 ( 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: java.base/jdk.internal の java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64) で、長さ 524289 の範囲外のインデックス 524289。 java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248) の util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70) 373) MultisetKt.main(multiset.kt:47) で java.base/java.util.ArrayList.get(ArrayList.java:426) で 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 に答える