範囲更新データ構造(改良版)
この前のは同じ色が連続してしまう可能性があったが、ちょっと考えれば防げるんじゃないかと思ってコードを書き直してみた。これで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はしていない。見つけ次第することにする。間違ってたら恥ずかしいから間違ってないことを祈る。