div2 only は省略．
A. The Fair Nut and the Best Path
燃料が負になることも許してパスを選ぶ問題を解けばよいです．途中で負になる経路は，そこから先のパスだけを残すことで改善可能だからです．あとは全方位木 dp などで解けます．
B. The Fair Nut and Strings
$s$ 以上 $t$ 以下であるような長さ $n$ の文字列 $k$ 個以下から作った trie の頂点数の最大値は？という問題．
仮想的にそのような文字列すべてからなる trie を考えます．深さ $d$ の頂点の個数を $n_d$ とすると，答は $\sum_d \min(n_d,k)$ です．葉がすべて深さ $n$ であることから，top-down に貪欲に $k$ 個のパスを作っていけます．
C. Max Mex
$v_i$ を $i$ が書かれている頂点とし，$f(l,r)$ を $v_l,\ldots,v_r$ の steiner tree がパスならばその端点，そうでないならそうでないことを示す何か．とすれば $f(l,m), f(m+1,r)$ から $f(l,r)$ が計算できます．たとえばパス $(a,b)$ とパス $(c,d)$ をマージする際にはこの 4 点の直径を計算し，すべての点が直径上にあるかを確認すればよいです．
結合できたのであとはセグメント木二分探索でできます．
D. The Fair Nut’s getting crazy
prv[i], nxt[i] を A[i] と等しいもののうち $i$ の手前や後ろにある最初のものの位置とします．
値がすべて異なる区間 $[i,j]$ について，これを共通部分とする場合の答えを考えると，$a = \max(prv[i],\ldots,prv[j])$, $b = \min(nxt[i],\ldots,nxt[j])$ を用いて $(i-a-1)(b-j-1)$ 通りです．
これを踏まえて $j$ をインクリメントしながら同じ $j$ に対する答えをまとめて計算する方法を考えます．$a[i], b[i]$ を上のように定めると，$a, b$ は区間代入により更新できます．すると，例えば $\sum a[i]b[i]$ は，$p,q\in\{0,1\}$ に対する $a[i]^pb[i]^q$ の sum を持つ遅延セグメント木で計算できます．他に $\sum ib[i]$ なども同じように計算して適切に足し引きすれば答が計算可能です．
E. The Fair Nut and Rectangles
長方形にネストがないということから，$x$ 昇順，$y$ 降順にソート可能です．
$i=1,2,3,\ldots$ 順に長方形を置いたり置かなかったりするとき，$i$ 番目の長方形を置いたときその時点でのスコア dp[i] を考えます．素直な二乗ループの dp がありますが，この式を書くと CHT により高速化できることがわかります．
F. The Fair Nut and Amusing Xor
まず a[i] xor b[i] だけが大事です．これを改めて a[i] とします．
区間への xor は b[i] := a[i] xor a[i+1] について，b[i], b[i+K] の 2 項に xor をするという言い換えができます．すると添え字 mod K ごとに独立した問題した問題と扱えて，以下のような問題がのこります：
- 列 a がある．2 種のクエリを処理せよ．
- a[i] の点変更
- a[i], a[i+1] の 2 項に同時に定数を xor する操作の繰り返しで a をすべて 0 にするためのコストを求める
さらに a をその累積和に置き換えると次のようになります．
- 列 a がある．2 種類のクエリを処理せよ．
- a の区間への定数 xor
- a[i] ひとつを好きに書き換える操作の繰り返しで a をすべて 0 にするためのコストを求める．
平方分割でこれに対応できます．
