【どう書く】高速・省メモリなセルのクリッピング塗り潰しアルゴリズムについて

gistfile1.txt

一次元配列X上に並んだ有限個のセルを考える。

  □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□ ...

これに、範囲オブジェクト(start, end)を与えると、
その範囲のセルが塗りつぶされる作用を持つ関数Fillを考える。

※ ここで、(start, end) は、start <= n < end を満たす
  インデックス n でアクセス可能なセル X[n] の集合を表現している。
  たとえば、範囲オブジェクト (3, 7) で表される領域には、
  3番目、4番目、5番目、6番目のセルが含まれるが、
  7番目のセルは含まれないことに注意してください。

1. たとえば、Fillに(10, 20)を与えると、10番目から19番目のセルが塗り潰される。

  Fill((10, 20))
  
  □□□□□□□□□■■■■■■■■■■□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□ ...
  
2. 次に、(30, 40)を与えると、30番目から39番目のセルが塗り潰される。

  Fill((30, 40))
  
  □□□□□□□□□■■■■■■■■■■□□□□□□□□□□■■■■■■■■■■□□□□□□□□□□□□□□□□□□□□□ ...
  
3. 次に、(22, 34)を与えると、22番目から29番目のセルがあらたに塗り潰され、
   重複して塗り潰しを指定された30番目から33番目のセルは、塗り潰されたままとなる。
  
  Fill((22, 34))
    
  □□□□□□□□□■■■■■■■■■■□□■■■■■■■■■■■■■■■■■■□□□□□□□□□□□□□□□□□□□□□ ...

上記のようなことをやるにあたって、

3.の操作のとき、(30, 34) の範囲が重複して塗り潰し指定されてしまっている。
ここで、塗り潰しのコストがものすごくでかいものと仮定して、重複を避ける方法を考えた。

そこで、「塗り潰したい範囲オブジェクト」を与えると、
「塗り潰すべき範囲オブジェクトのリスト」が返る関数Guessを
作ればいいんじゃないかと考えた(動機の説明ここまで)。

Guess関数の説明

1. Guessに(10, 20)を与えると、範囲オブジェクトのリスト[ (10, 20) ] が返る。
  (リストは[]で表すものとする)
  
  ranges = Guess((10, 20))  # ranges == [ (10, 20) ]

2. 次に、Guessに(30, 40)を与えると、範囲オブジェクトのリスト[ (30, 40) ] が返る。

  ranges = Guess((30, 40))  # ranges == [ (30, 40) ]
  
3. 次に、Guessに(22, 34)を与えると、範囲オブジェクトのリスト[ (22, 30) ] が返る。
  
  ranges = Guess((22, 34))  # ranges == [ (22, 30) ]

  ※ ここまでで注意して欲しいのは、Guessは副作用を持つ関数で、
    以前までに与えられた範囲オブジェクト (10, 20)、 (30, 40) を、なんらかの形で覚えている。
    以前までに指定された部分を除けて結果を返している、ということです。

4. さらに、Guessに(5, 50)を与えると、範囲オブジェクトのリスト
   [ (5, 10), (20, 22), (41, 50) ] が返る。

   複数の要素を持つリストが返る場合、それらの要素間には範囲の重複が無く、
   かつ昇順にソートされているものとする。
  
  ranges = Guess((5, 50))  # ranges == [ (5, 10), (20, 22), (41, 50) ]

このような仕様の関数Guessを、なるべく高速に、かつメモリを使わずに書きたい。
たとえば、Guessの内部にビットマップ的なものを持たせて、
全セルの個数に対して線形オーダーでメモリを食うような実装は、どんなに頑張ったとしても、だめです。

全セルの個数に対しては、できれば定数オーダー。
以前までのGuessの呼び出し回数に対して、線形オーダーなら、よしとする。

あと、範囲オブジェクト(start, end)自体は、内部に整数値を2つ持つオブジェクトで、
占有するメモリはわずかです。

言語はなんでもいいですが、勝手に並列化が効くような処理系を想定した場合、
計算量や計算時間についての注釈があるとありがたいです。