A. Against the Difference
$[0,i)$ から neat subsequence をとるときの最長を $\dp[i]$ として計算．
末尾の項 $A[i]=k$ を決めたときには，$k-1$ 個手前の $k$ の出現位置を見て遷移します．
B. For the Champion
- 右右上上に $10^9$ 進んで値を聞く．この時点での $x+y$ が手に入る．
- そこから下下下下に $10^9$ 進んで値を聞く．この時点の $x-y$ が手に入る．
C. By the Assignment
walk の場合とは結構事情が違います．木だと何も条件がないのでまずはサイクルに注目します．
すると，サイクル上では定数列になっていること，さらに奇サイクルならばすべて $0$ であることが分かります．
二重辺連結成分分解をすると，各連結成分について定数です．この成分が二部グラフか否かに応じて「すべて $0$」「定数だったらなんでもいい」というタイプの条件があるということになります．
D2. From the Unknown (Hard Version)
まずは，$(X,X,X,\ldots)$ （$Y$ 個）という質問をします．
このとき，$W<X$ については何も区別されません．
$W\geq X$ については，$\lceil Y / \lfloor W/X\rfloor\rceil$ が等しいような $W$ が区別されません．
- $W<X$ への対処：$2$ 回目で $(1,1,1,\ldots)$ を質問する．おおよそ $X^2$ 個程度あると，商がばらけて値を確定できる．
- $W\geq X$ への対処：絞り込めた区間を $[L,R]$ として，$L, 1, L, 2, L, 3, \ldots, L,R-L$ というように質問する．あるところまで $2$ 個組，そこから先は $1$ 個組でとることになって，そこ境界から $W$ が特定できる．
前者の場合に上手くいくように，$Y=25000-X^2$ 程度にとり調整すると，すべての $W$ でうまくいくパラメータが見つかります．なお D1 については $X=1, Y=100000$ でよいです．
E2. Beyond the Palindrome (Hard Version)
どちらの操作をしても，残るのは $0000111111$ のタイプの文字列で，残る $0$ の個数が問題です．この個数は，$1$ を $+1$，$0$ を $-1$ に置き換えた列の累積和の $\min$ から分かります．
これを整理すると，次のような問題になります：
- 長さ $N$ の $+1,-1$ の列であって，sum = min + max となるものを数えよ．
min が $0$ であるように調整すると，次のような感じです．
- すべての $a,b$ について次の総和：$(0,a)$ から出発し $(N,b)$ へ到達する dyck path であって，道中の $y$ 座標の min, max が $0, a+b$ であるようなものの個数．
これでひとまず $N$ の多項式計算量にはなります．
$min, max$ が $[L,R]$ というのは，適当な包除で「$L-1,R+1$ を通らない」「$L-1,R$ を通らない」「$L,R+1$ を通らない」「$L,R$ を通らない」等に分解できます．そして，それぞれは鏡像原理で数え上げが可能です．
例えば「$L,R$ を通らない」であれば，
- $i\equiv a\pmod{2(R-L)}$ であるときに $(0,i)$ から $(N,b)$ へのパスの個数を足す．
- $i\equiv 2L-a\pmod{2(R-L)}$ であるときに $(0,i)$ から $(N,b)$ へのパスの個数を引く．
のようになります．$d=R-L$ とすると，それぞれのパートは，「$i\equiv c(d,a,b)\pmod{d}$ のときに $\binom{N}{i}$ を足す」というような形になります．
ここから $a+b$ を固定して $a$ を動かすと，「$i\neq c(d)\pmod{2d}$ のときに $\binom{N}{i}$ を足す」というタイプの計算に帰着できることが分かります．$\pmod{d}$ でほぼ $1$ 通りの部分を足し続けたり，ほぼ全通りを足し続けたりすることになるからです．
これをすべて計算すると，$d=a+b$ ごとに $O(N/d)$ 時間で計算できて，全体で $O(N\log N)$ 時間で解けます．これで E1 が解けます．
E2 はここからさらに計算量を改善することになります．
E1 の計算をより詳しく見て，$\binom{N}{i}$ の答への寄与を取り出すと，
- $2i-N$ が $d$ の奇数倍であるときに $\binom{N}{i}$ の寄与を $a_d$ 増やしてください
というタイプの計算が登場しています．しかもこの $a_d$ は $N$ に依存しません．
このような係数を得るには，「$d$ の倍数のところに $a_d$ を足し，$2d$ の倍数にところから $a_d$ を引く」というようにすればよいので，約数ゼータ変換で $O(N\log\log N)$ 時間で計算できます．
私はここでも TLE になっていました．ここでの係数列の計算は $N$ に依らないことが分かる（ただし私は parity ごとに解くことにはなった）ので，これをまとめて計算してしまってからクエリをさばくことで，約数ゼータ変換の計算量にかかる計算量を $\sum N$ ではなく $N_{\max}$ にできて，間に合いました．
自分の実装だとかなり TLE にギリギリで，いろいろと高速化の技を繰り出す必要がありました．
F. To the Infinity
正の無限大に発散する関数 $F_1(x), F_2(x)$ に対して $F_1$ が $F_2$ より「とても大きい」とは，任意の正整数 $n$ に対して $\dfrac{F_1(x)}{F_2(x)^n}\to \infty$ となることと定義します．
次が成り立ちます．
- $A_i(x), B_j(x)$ のうちどの $2$ つについても，完全に等しいか，どちらかがもう一方よりもとても大きいとする．とても大きいという関係について $A_1, A_2, \ldots$, $B_1,B_2,\ldots$ が降順であるとする．
- $A(x)=pow(x, A_1(x)A_2(x)\cdots)$, $B(x)=pow(x,B_1(x)B_2(x)\cdots)$ とする．このとき，$A, B$ は完全に等しいか，どちらかがもう一方よりもとても大きいかのいずれかである．この大小は列 $(A_1,A_2,\ldots)$ と $(B_1,B_2,\ldots)$ の辞書順と一致する．
証明は簡単です．
これで何らかの多項式時間アルゴリズムにはなります．各頂点での関数を $pow(x, A_1(x)A_2(x)\cdots)$ のように書くことが重要です．ある頂点でのこの表示は，left child におけるそれに，right child におけるそれを挿入することで得られます．すると，$u, v$ の subtree がすべて値が比較出来ているとき，$u, v$ の比較ができます．多項式時間で最小の頂点から順に決めていくことができます．
具体的には，
- 葉にランク $1$ および，空の列を割り当てる．
- 左右の子のランクが確定している頂点に，列を割り当てる．左の子の列に，右の子のランクを挿入したものとする．この頂点のランクは未定であるとする．
- ランクが未定の頂点に対して，列を降順ソートしたときの辞書順比較で最小の頂点を調べる．この頂点に，今まで割り当てたランクの値に $1$ を加えた値のランクを割り当てる．
という要領です．
動的セグメント木にローリングハッシュをのせて，比較では $2$ つのセグメント木を同時にもぐるタイプの二分探索するタイプをすることで，$O(\log N)$ 時間に高速化できます．最小値の取り出しを priority_queue などで行うところにもうひとつ $\log$ がついて，全体で $O(N\log^2N)$ 時間で解けます．
左の子のノードへ挿入したものを新しいノードとしますが，この操作を行う時点で左の子のノードはもう不要になっているので，永続化する必要はありません．
