範囲更新データ構造

色塗り問題を解くデータ構造を勉強してみた。

Makegumiライブラリを参考にさせていただいて、何やっているか理解し、改めて自分で書いてみた。Makegumiには合宿3日目の最大流のときから本当にお世話になっている。
fromの情報だけあればtoの情報が要らなくなるところがポイントだなぁ。
PKU2528でvarifyしてあるがconnectについてはしていない。

typedef int color_t;
typedef map<int,color_t> region; //region[from] = color

//[from,to)を塗りつぶす。領域の左端を無色で初期化しておくこと。
//同じ色が連続してしまう可能性のある実装。必要なら最後にconnect処理をする。
void paint(int from, int to, color_t color, region& r) {
  if (from >= to) return;
  color_t c = (--r.upper_bound(to))->second;
  r[to] = c;
  r[from] = color;
  r.erase(++r.find(from), r.find(to));
}

void connect(region& r) {
  region::iterator it = r.begin(), end = r.end();
  for (color_t prev_color = (it++)->second; it != end; ) {
    if (prev_color == it->second) r.erase(it++);
    else { prev_color = it->second; ++it; }
  }
}