A. Short Program
各ビットが 0 から始まったときと 1 から始まったときの最終的な値を計算しておきます．出力は or, xor の 2 行で行えます．
B. Teams Formation
列の長さを計算量にしてよいならば，スタックを用いて左からシミュレーションすればよいです．
このとき，「同じ $a_i$」が別の成分として 2 回入ることがあれば，以降のシミュレーションでその間の部分が繰り返されます．なので，スタックの中身は最新の $N$ 個の成分しか見なくてよいです．
このような観察をもとに binary lifting で列の prefix, suffix だけを $N$ 成分だけ残しながら binary lifting で計算します．
C. Tournament
scc はパス状になります．特に種目 $0$ の強い方からインデックス付ければ，成分は区間に分かれるのでこれを管理します．（左から右に向かって topological 順）
各成分と各種目に対して成分内の最強と最弱を持っておきます．新しい頂点が来たとき，その頂点に入る辺は最も右側から来るものだけ，その頂点から出る辺は最も左側から来るものだけ考えればよいです（それ以外の辺は既存の辺の繰り返しで作れる）．この範囲を求めて間の成分を併合することで新しい強連結成分分解が得られます．
D. Magic Breeding
二分探索を行うことを考えます．するとすべての値が 0, 1 のどちらかであり，初期の $k$ 人がそれぞれ 0, 1 のどちらであるかによってクエリされている人の値を計算するという手順が発生します．
「初期の $k$ 人の 0, 1 列」は $2^k$ 通りしかありません．そこで，そのすべての場合に対して各人のもつ 0, 1 がどちらになるかを前計算しておきます．するとクエリごとに高速に二分探索を行えるようになります．bitset 高速化が可能．
E. Numbers on the blackboard
まず正しい解を得る方法を考えます．
各値は係数 $1, 2, 4, \ldots$ のどれかでとることになります．右端の値が負である場合，これは係数 $2$ でとるとしてよいです．手順としては最後にこれをマージします．
そうでないとき，右端の値は初手で隣とマージしてしまうのが最適であることが示せます（帰納法と exchange argument）．
よって，列の長さが 2 以上である間
- 末尾が負ならばその 2 倍を ANS に加えて末尾を pop
- 末尾が非負ならば末尾を pop して，その 2 倍を新しい末尾に加える
というアルゴリズムが最適解を与えます．これを高速化します．
まず，各 $i$ に対して，右端の要素が $i$ である状態から上のアルゴリズムを使ったときにどこではじめて「末尾が負ならば」のルールが適用されるかを求めます．これが求まったとすると，区間クエリは典型的な木の二分探索になります．
「末尾が負ならば」が適用される場所というのは，$\sum 2^ia_i$ の区間和が負になる場所と言えるので，簡単なセグメント木二分探索になりそうですが，非常に巨大な数が出てきてしまうという問題に対処しなくてはいけないのでここも難所です．
$j$ をインクリメントしながら $b[i] = \left\lfloor\sum_{i\leq k\leq j}a[k]2^{j-k}\right\rfloor$ という列を管理することを考えます．この値は常に 31 bit 程度に収まります．
列には $x\mapsto \lfloor x/2\rfloor + a$ を作用させるという形になります．このような形の関数の合成は常に $x\mapsto \lfloor(x+a)/b\rfloor+c$ という形に書けます．この $a,b$ は巨大になる可能性がありますが，常に十分小さな $|x|$ しか現れないという前提のもとで大きさ $O(1)$ のデータで表すことができます．これを作用として区間 min の遅延セグメント木二分探索をすれば「末尾が負ならば」が適用される場所を求めることができます．
