A. Games on the Train
max + 1 にあわせます．
B. Tatar TV Show
添字を $K$ を法として分類します．隣接 $2$ 個 flip という条件になります．
$1$ の個数の偶奇が不変量．先頭以外を $0$ にできるので，個数が偶数のとき全部 $0$ にできます．
C. Omsk Programmers
大きい方に対して除算しない場合は解けます．除算する場合は除算してから解いたものに $+1$ したものです．
D. Brand New Tatar TV Show
ある異なる値 $x,y$ について，$0 < y-x \leq k$ であるとします．
$y$ スタートが後手必勝ならば，$y$ を選びます．そうでないならば $x$ を選びます．
結局，このときどちらかが目的の値として選べます．
この場合を処理すると，残ったケースは最初に選んだ値と同じ値を選び続けるしかないという入力しかありません．これは適当な偶奇が条件です．
E. Friendly Gifts
区間 $[L,R]$ が good であるかは，
- 種類が異なることと
- min, max との差から分かります．
$L$ を固定するごとに計算すると思えばひとつあたり $O(1)$ 時間で計算できます．
good であるような区間の値区間 [min,max] を列挙しておけばあとは解けます．
なんと good 判定を min, max の差だけ見ても AC だったんですが，Hack 可能ですよね．（[1,1,4,4,5,5,8,8] など）
F2. Elections in Saransk (hard version)
重要なのは素数ごとに独立に解けるということです．約数を選ぶというのは，素数ごとにその指数を独立に選ぶということですし，lcm や総積も素数ごとに分解できます．
結局，「列 $(a_0,a_1,\ldots)$ がある．各 $i$ について $0\leq x_i\leq a_i$ を選べる．sum から max を引いたものを指定のものにする方法は何通り？」とかです．
「max がいくつ以下の場合の数え上げ」というのを適当な範囲でやります．
sum や $a_i$ の上限を $K$ として，$p$ ごとに $O(K^2 \cdot n)$ （$n$ は $p$ の倍数であるような入力の個数）くらいです．$K$ が大きいような $p$ は少ないので，余裕があります．
G. Criterion in Burlandia
これはいわゆるセグ木に乗る形です．とりあえず木じゃなくて列の問題だとしましょう．
- 区間に対する ANS
- prefix から見て条件が矛盾しない間で，どのような sum が何回現れるか（最大長 20 程度のペア列）
- suffix から見て条件が矛盾しない間で，どのような sum が何回現れるか（最大長 20 程度のペア列）
よって HLD などでも行けると思うんですが，計算量が結構心配です（とコンテスト中は思ったんですが，大丈夫かも）．
結局，重心分解の形で処理しました．
prefix, suffix に関する配列を vector, array どちらで持つかとかもかなりパフォーマンスに影響しました．
