Codeforces Round 1059

A. Beautiful Average

$1$ 要素だけの場合を調べればよいです．

片方の文字種をすべて集めればよいです．

$2^k\leq a< 2^{k+1}$ となる $a$ をとり，$c=2^{k+1}-1$ とすると，

となります．

$2$ 種のクエリの差分をとることで，$[0,l)$ 内で行われた加算回数が取得できます．

よって，二分探索により $2\log_2n$ 程度の回数で $l$ が求まります．

$r$ を求めるのも同じ二分探索をしてしまうと，クエリ回数が足りません．

列全体にクエリすれば，列全体で行われた加算回数も分かるので，この回数と $l$ から $r$ が求まります．

$n+1$ 項目以降では，各項についてその項を含む長さ $2$ 以上の回文が存在しないようにします．

$3$ 種の $x,y,z$ によって，$a_1,a_2,\ldots,a_n,x,y,z,x,y,z,x,y,z,\ldots$ とします．

$a$ に現れない数があるならばそれを $x$ とすればよいです．

$a$ が順列ならば直前の数項を見て $x,y,z$ を決めればよいです．

$0,1$ を両端に置くと，$v_j\neq 2$ にできるので，答は $2$ 以下です．特に $0,1$ にできるかを検討すればよいです．

$p_i=0$ とする $i$ を全探索します．$i\notin [l_j,r_j]$ となる $j$ では自動的に $v_j=0$ となります．このような $j$ がなければ $ANS=0$ 達成です．

そのような $j$ があるなら，$v_j\geq 1$ となるすべての $j$ で $v_j\geq 2$ にできるかを考えます．

まず $2$ を根とする根付き木を作ると思い，

とします．すべての親を $2$ にした状態から，親をインクリメントする操作を考えて調整できます．

根を $2$ としたのは，$v=1$ での調整をしやすくするためですが，根を $1$ としても同様の解法は可能だと思います．

まず $x$ を固定したときのことを考えます．このとき，数は $x$ との大小関係によって $-,0,+$ の $3$ 種類だと思って構いません．「$-,+$ の両方を含む区間が存在しない」というのが条件となります．

まず，$\mathrm{dp}[pos][val][cnt_{-}][cnt_{+}]$ を true, false のどちらかの bool 値とする dp が考えられます．$pos$ は位置で，$val$ はその位置での最後の $+, -$，$cnt_-$ はそこまでの $-$ の個数です．

この dp には単調性があって，

という dp が考えられます．これで計算すべき値を $O(N^2)$ 個にできました．

$[0,i]$ における valid な定め方について，最後の $0$ 以外の要素を右に移動させても valid であることに注目すると，

直前においた $0$ でない項が次に置く $0$ でない項と同じとき：$\mathrm{dp}[i]$ から $\mathrm{dp}[i+1]$ への遷移を考える．
直前においた $0$ でない項が次に置く $0$ でない項と逆のとき：$i$ と同じ区間に入るような最小の $j$ をとり，$\mathrm{dp}[j]$ から $\mathrm{dp}[i+1]$ への遷移を考える．

というタイプの遷移だけを考慮すればよいことになります．