競技プログラミング用 知識集積所
ABC415F - Max Combo
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
問題は[l,r]で与えられるが、rに1を足して[l,r)で考える。
区間境界さえ管理しておけば、大まかに以下のような発想で解けそうな気がする。
区間境界さえ管理しておけば、大まかに以下のような発想で解けそうな気がする。
siを文字が変わる境界の位置として、
……<s1<l≦s2<s3<s4<r≦s5<……
となっている場合、
s2-l,s3-s2,s4-s3,r-s4の最大値を答える。
……<s1<l≦s2<s3<s4<r≦s5<……
となっている場合、
s2-l,s3-s2,s4-s3,r-s4の最大値を答える。
しかし、ぐちゃぐちゃな文字列だった場合に長大な範囲を指定されると計算処理が重い。
そこで、
そこで、
- s2-lとr-s4は個別計算にする
- s3-s2,s4-s3は最大を求めるsegment木（未作成）を頼る
という方針で間に合わせる。
これを実現するためには、
- 同一文字列領域の両端を管理し、ある位置を含む区間をパッと出せるようにしたもの
- 同一文字列領域の長さを適切に格納したsegment木（未作成）
の両方を用意して、クエリ1が来るたびに気合でこれらを更新し続ける。
適切な位置は、領域内のどこでもいいが、同一文字列領域の両端として管理している位置に入れておくとまだ多少は作業しやすい。
適切な位置は、領域内のどこでもいいが、同一文字列領域の両端として管理している位置に入れておくとまだ多少は作業しやすい。
あとは気合。
実装が超重い。
実装が超重い。
解答例
注意点
クエリ2で全部同一文字の区間が来た場合に注意
文字が変わる境界の位置とlやrの位置関係が、
……<s1<l<r<s2<……
となっている場合は、答えはr-lである。
このパターンで変な答えを出さないように注意が必要。
……<s1<l<r<s2<……
となっている場合は、答えはr-lである。
このパターンで変な答えを出さないように注意が必要。
