ACLBC E - Replace Digits (500)
想定解法は遅延セグ木だが平方分割で解いた
愚直にQ個のクエリを処理すると、$ O(NQ)となり$ NQ \gt 10^{10}になりうるのでTLEする
10の0乗からN乗までを事前に求めておく
区間内全て1の場合の値を求めておく
文字列を長さ500で最大400個の区間に分割する
区間毎にその範囲内の文字列からできる数を事前に求めておく
全て1なら$ \sum^{500}_{i=1} 10^{i-1}になる
区間内の全ての文字が同じかどうかのフラグと同じ場合の文字を記録しておく
それぞれのクエリで以下を行う
左端と右端で区間全部を覆わない部分は一文字ずつ更新し、区間内でできる数値を差分から毎回更新する
全ての文字が同じフラグが立っている場合はフラグを消して、それぞれの文字を同じとして記録されている文字で更新
区間全体が覆われている部分においては区間全体を一括で更新する
全ての文字が同じフラグを立て、その文字を更新する
区間から作れる値は区間内全て1の場合の値にその区間の文字を書けたものになる
最後に各区間から作られる値を合計してクエリ後の値とする
全てが覆われていない区間は高々2つなので更新はおおよそ$ O(\sqrt{N})
全てが覆われている区間の更新はそれぞれ$ O(1)なので全区間合わせておおよそ$ O(\sqrt{N})
全体で$ O(Q \sqrt{N})になって間に合う