A
interactiveなので二分法を考えると、極小値が存在する区間を半分ずつ絞れることがわかる
B1
数列を順番を保ったまま二つに分解し、それぞれランレングス圧縮した後の長さのmaxを求めればよい
とりあえず適当な貪欲を書く
順位表を見て反例がありそうな気持ちになるが、手元で作れなかったので提出→WA
もう少し反例を考えたが出てこなかった、こういうときはDP?
数列を左から分解していくことを考える
作られる二つの列のうち、少なくとも片方の先頭は直前の数になっている
↑そこそこ強い性質じゃないか？
dp[どこまで見たか][二つの列の先頭がどちらも同じか]を考えるが、遷移先が定まらない
遷移に足りない情報を考えると、直前の数を置いた方でない数列の先頭の数があればよいことがわかる
数列の要素 <= 10^5なのでそのまま状態に持てそう
dp[直前の数を置いた方でない数列の先頭]=maxとすると、セグ木で遷移できる
→区間加算は区間全体への加算しかしないので、この加算分を別に保持しておけば普通のセグ木でできる
数列の要素の上限が10^9とかではなく10^5ぐらいになっているとき、この制約の必要性からある程度方針をメタ読みできる（パケットを作るetc...）
とりあえず必要そうな情報を全て持ってDPを考えて、そこから本当に必要な情報を絞っていくのがよさそう
うまくやると貪欲にできる（先頭がそれぞれx,y、新しく入れる要素がzのとき、次に来るx,yの位置を参考にzを入れる列を決めていく）
B2
B1とほぼ同様にできる
C
二進法で数を網羅する（構築でよくあるやつ）
適当に作ったら、実装しながら無限場合分け地獄であることに気づく
最初から単純に書こうとするより、とりあえず全て場合分けをしてから整理する方がよさそう