ICPC 2019 Asia Yokohama Regional-C Wall Painting (AOJ 1402, 800)

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 の6日目の記事です．

問題リンク

onlinejudge.u-aizu.ac.jp

概要(0-indexedに変換後)

横に並んだ $N$ 個のマス目があり， $0, \ldots, N-1$ の番号がそれぞれついている． $i\ (0 \le i \lt m)$ 番目のロボットを作動させるとマス目 $l_i, l_i + 1, \ldots, r_i-1$ を色 $c_i$ で塗る．ロボットの動作後のそれぞれのマス目の得点は，そのマス目に塗られた色が0種類であれば0点，1種類であれば $x$ 点，2種類以上であれば $-y$ 点となる．作動させるロボットを自由に選んで良いとき，得点の合計の最大値を求めよ．

制約

問題リンク先を参照．

解法

色の種類が少ないことは使いそう．

基本的に SWAG みたいな色の塗り方をするとして問題ない． $l_i$ の昇順に処理する $O(m)$ の遷移はまあ明らかで，これをRMQセグ木で高速化する．塗りの重なる部分は，1マスにつき同色ならば $x$ ，違う色ならば $2x+y$ だけ損をするので，セグ木の更新時にはこれをあらかじめ引いた値を突っ込むことで適切に大小比較できる．