グリッド L*C (L と C は 0 から 1.000.000.000 の範囲) 内の N 個の四角形 (N<=100.000) の座標を考えると、グリッド内の任意の点で重なる四角形の最大数を知りたいです。
そのため、x 値でソートされた各イベント (長方形の開始または終了) に対して、スイープ アルゴリズムを使用すると考え、構造に間隔を追加または削除します。
間隔の最大の重なりを維持し、間隔を追加および削除できるようにするには、ツリーを使用する必要があります。
間隔 (開始と終了) の値が 0 から 100.000 の範囲にある場合の方法は知っていますが、平面の次元が 0 から 1.000.000.000 であるため、ここでは不可能です。どうすればそのようなツリーを実装できますか?
すべての長方形の座標が事前にわかっている場合は、「座標圧縮」を使用できます。
10^5 の長方形しかないので、最大で 2*10^5 の異なる座標があることを意味xします。yしたがって、これらの座標から 1 から 2*10^5 までの自然数へのマッピングを作成できます (単に座標を並べ替えるだけです)。次に、新しい座標に対して既に知っている通常のツリーを使用できます。
四角形の数を取得するにはこれで十分ですが、それらが重なっている点も必要な場合は、四角形の実際の座標に戻れるように逆マッピングも維持する必要があります。一般的な場合、答えはただの点ではなく四角形になります。
区間木を使用します。重みがその間隔の開いている長方形の数である重み付き区間ツリーが本当に必要なため、ケースはもう少し複雑です。