C
N^2未満の解法はぱっと思い浮かばない
lごとに累積minを持ちながらl,rを全探索、でになるが、ABC-Cで10^8は見たことが無い
の意図がよくわからない
を見てxの全探索を考える
xの値ごとに、全ての要素がx以上であるような区間の長さのmaxを求めればよい
xを降順に見ると、全ての要素がx以上となっている区間が次第につながっていくことが分かる
→UnionFindでやる
冷静になると最大長方形問題
長方形の右上端を全探索、左下端を探す時にstackでよしなにやるとでできることが有名
D
問題文に漸化式が書いてあるのでDPを考えたい
N=60で踏みとどまる
数え上げなのにmodを取らない設定、[2^60 \leqq LONG_MAX]を意図していそう？
じゃあDPでいいか
dp[y_iが][0か1か] として計算
y_iが0のときはi以下のxはなんでもよいので、一次元でよかった
E
とりあえず式にするべき
(x,y)に対する変換操作を整理すると、x,yのswap、係数の反転&定数項の加算からなることがわかる
→x,yがswapされた回数と、x,yの係数、定数項の値を持って変換結果の累積を持っておけばよい
累積を持っておけば十分であることに気づかず、クエリをaでソートしたりしていて燃えていた
書くことが多いと処理を忘れがち、まとめておくのがよさそう
ちょっと重めの実装に慣れていないので、こういうのが出ると早解きに失敗してよくない
F
とりあえず期待値の線形性を考えたい、各マスから移動する回数の期待値を求めればよい？
→うまくいかなかった
マスN-1の結果は明らかなので、マス目のindexに対し降順にDPをすることを考える
マス[i]からスタートする場合の合計操作回数を順に求められたらハッピー
振り出しに戻るマスの遷移式でE_0が出てきて、遷移式が循環して困る
→式変形をして循環を消したい
単純に移項するだけ（期待値を求めるときによく見る）では消せない
とりあえずdp[0]をxと置いてDP遷移をすると、各dp[i]はxの一次式になっていることがわかるので、この式の係数をDPで求めればよい
E_0がE_0の一次式で書けるので、単純に移項するだけになる
貰うDPを書いたら、遷移のindexで大変なことに...
dif2000以上の考察・実装が2000未満より明らかに遅い、春休みはここを何とかしたいな