範囲更新データ構造(改良版)

この前のは同じ色が連続してしまう可能性があったが、ちょっと考えれば防げるんじゃないかと思ってコードを書き直してみた。これでconnectがいらなくなった。

"upper_bound(x)"は「xより上」のxに最も近い値を指すイテレータを返すので、"--upper_bound(x)"が「x以下」のxに最も近い値を指すイテレータを返すということを元に考えてみた。

eraseする場所を早めに持ってきたところがポイント。

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

//[from,to)を塗りつぶす。領域の左端を無色で初期化しておくこと。
void paint(int from, int to, color_t color, region& r) {
  if (from >= to) return;
  color_t c = (--r.upper_bound(to))->second;
  r.erase(r.upper_bound(from), r.upper_bound(to));
  if (c != color) r[to] = c;
  if ((--r.upper_bound(from))->second != color) r[from] = color;
}

コードをチェックするちょうどいい問題を見つけていないため、varifyはしていない。見つけ次第することにする。間違ってたら恥ずかしいから間違ってないことを祈る。