A. MAD Interactive Problem
まず $2n$ 回で，それぞれひとつずつ見つけます．
$I$ をある値の $1$ 回目の出現位置全体として，
- $I\cup\{i\}$ で $0$ が返ってきたら $I$ に $i$ を追加
- $I\cup\{i\}$ で $a>0$ が返ってきたら $ANS[i]=a$ と確定
というようにすると，$2$ 回目の出現が全部見つかります．
あとは，$2$ 回目の出現全体を $I$ として，未知の $i$ に対して $I\cup \{i\}$ をクエリしていけば，$1$ 回目の出現も決まっていきます．
B. Rectangles
$n<m$ を仮定します．
$u,d$ を固定するごとに解くことを考えると，列として使える場所 $j_1,j_2,\ldots$ が確定します．
あとは $[u,d]\times [j_k,j_{k+1}]$ 部分に何らかの chmin する．という処理をしたいですが，これを愚直にやると TLE すると思います（適切なデータ構造の $\log$ はつけても大丈夫かも）．
$u$ を固定して，$d$ を降順に処理します．すると，ある列への chmin は以降の行でも保持し続けてよいことになるので，この結果を列ごとに保持しながら $d$ をデクリメントしていけばよいです．計算量は $O(n^2m)$ です．
C. Twin Polynomials
サンプルの最後の $3$ つがなかなか見つからない！$[6,3,0,1,0,5]$ を発見することが重要．$ax^0$ は $0x^a$ に変換されますが，ここだけは $a>n$ でも大丈夫なんですね．
$a[0]$ は $f(1)=0+1+\cdots+n$ から一意に決まるので，$a[1],…,a[n]$ を決めることを考えます．
$a[i]\neq 0$ とした $i$ については，$a[i]=i$ またはマッチング（$a[i]=j, a[j]=i$）になっていないといけません．これで条件は全部です．
$a[n]\neq 0$ を数えますが，これは $a[n]$ を自由にした場合と $a[n]=0$ を強制した場合の差として処理します．
あとは，$n$ 頂点を「孤立点にして重みを $2$ 倍（$a[i]=0,a[i]=i$」「$i,j$ でマッチング」などに分割する方法の数え上げに帰着されます．
D1. Inverse Minimum Partition (Easy Version)
$\dp[j] = \dp[i] + \mathrm{cost}(i,j)$ の形の計算をすればよいです．
分割統治で処理します．$[L,R)$ の区間のうち $M$ をまたぐもの $[i,j)$ による遷移を考えます．
左右どっちの区間に $\min$ があるかで場合分けをします．
右の区間に $\min$ がある場合が簡単で，各 $j$ に対応して右に $\min$ があるという条件下（$i$ の範囲）での $\dp[i]$ の最小値がとれればよいです．
左の区間に最小値がある場合には，$f_i(x)=\frac{x}{a_i}+b_i$ のような関数の $\min$ を考えることになります．
これを LiChao Tree で処理しました．
私の解法の計算量は $O(N\log^2N)$ 時間です．
D2. Inverse Minimum Partition (Hard Version)
この答ができるということはこういうことになるというメタ読みが出来ると解きやすい．query(l,r) 問題とかの方が難しいかも．
結論からいうと，次の重要な性質があります．$\mathrm{cost}(i,j)$ は区間 $[i,j)$ のコスト．$\mathrm{ANS}(i,j)$ は $[i,j)$ に対する答です．
- $\mathrm{ANS}(i,j)\geq \mathrm{ANS}(i+1,j)$．
- $\mathrm{ANS}(i,j)\leq 2\log_2A$．
- $\mathrm{cost}(i,j)\leq 3$ となる $(i,j)$ だけを考えればよい．
最初の性質を示すには，単に $\mathrm{ANS}(i+1,j)$ の解を与える先頭のブロックの先頭に $1$ 要素追加することを考えればよいです．
私は最初の性質に気づいたあと，問題を列全体を reverse して考えました．コストは先頭の項を $\min$ で割る形です．以下このようにして扱います．
$2$ 番目の性質は，先頭の要素を $a$ として，「次に $a/2$ 未満の項が初めて現れるところ」で列を分割していくことで示せます．
$3$ 番目の性質は，$\mathrm{cost}(i,j)\geq 4$ となる $[i,j)$ を細分することで示せます．具体的には $(a,\ldots,b,\ldots)$ という区間があって $b$ がこの区間の $\min$ であるとき，はじめて $2b$ 以下の要素が現れるところで列を細分することを考えると示せます．
以上により，おおよそ次の手順が想定できると思います．私の実装では reverse して考えることで $\mathrm{ANS}(i,j)\leq \mathrm{ANS}(i,j+1)$ にしていることに注意してください．
- $0\leq i\leq N$ と $0\leq k\leq 2\log_2A$ に対して，次の値を $\mathrm{dp}[i][k]$ とする： $\mathrm{ANS}(i,j)\leq k$ となる $j$ の最大値．
- $i$ について昇順にこれを計算する．$i$ を始点としてコストが $1, 2, 3$ 以下になるような遷移を行う．
このような方針で，全体として $3N\cdot 2\log_2A$ 回程度，何かの計算が出来ればよいという解法が出来ます．
あとはこの「何かの計算」についてきちんと考えると，これは静的な列に対する RMQ ということになります．$6\log_2A$ が結構大きいので，ある程度高速なアルゴリズムを使う必要があるかもしれません．
単調 stack と 64 分木，あるいは高速な static rmq などを持ってくると AC できました．
E. Super-Short-Polynomial-San
コンテスト中の AC 人数は少なかったですが，かなり簡単だと思います．
類題は $(1+x)^n$ の係数 prefix sum の計算で，適当な平方分割での $1.5$ 乗系の解法が有名でしょう（なおオフラインならやや難解な $(N+Q)\log^2(N+Q)$ 系の解法があります）．
本問題もそんな感じでできます．適当な$B$ をとり，
- $B\mid N$ に対する $f(x)^N/(1-x)$ を計算しておく．sparse fps pow で $N$ ごとに $O(N)$ 時間．
- $n\leq B$ に対する $f(x)^n$ も計算しておく．$O(n^2)$ 時間．
- クエリに答えるには，$f(x)^{qB+r}/(1-x)=f(x)^{qB}/(1-x)\times f(x)^r$ と分解する．$f(x)^r$ の係数が $O(r)$ 個しかないので $O(B)$ 時間．
とすれば $O((N+Q)\sqrt{N})$ 時間（$N$ はクエリが来る $n$ の最大値）となります．
F. Grand Finale: Snakes
結論として関数 $F(L,-)$ について，次の性質があります：
- $O\left(\frac{N}{L}\right)$ 個の単調増加列または単調減少列に分割できる．
まずこのような列に $120N$ 回以下のクエリで分割してしまって，そのあと各列の先頭や末尾からとっていくというのが解法の流れになります．
分割パートについて確認します．証明は簡単で，「一度増加したら，次に減少するまでに $L$ 項以上かかる」という性質から示せます．
この分割はさらに，$O(\log_2 N)$ 回で決定できます．主要なアイデアは次の通りです．
単に $f(x) = F(L,x)$ と書きます．また問題設定より $f(x) = \max(A_{x},\ldots,A_{x+L-1})$ となる $A$ があり，$A$ の要素は distinct です．
- 区間 $[a,b]$ に注目する．
- $f(a)=f(b)$ ならばこの間は定数であるので終了．
- $f(a)$ の $A$ における位置を $p_a$，$f(b)$ の $A$ における位置を $p_b$ とする．$x\in [a,p_a]$ において $f(x)\geq f(a)$，$[b,p_b]$ において $f(x)\geq f(b)$ である．
- $b\leq p_a+1$ のとき，$[a,b]$ はこの $2$ 種の区間で被覆されている．この区間において $f$ は単調であることが言える．次のことをあわせて考えると示せる．
- $b\leq p_a+1=a+L$
- $f$ は $1$ 回増えると $L$ 回は減らない
- 区間全体で $f(x)\geq \min\{f(a),f(b)\}$ より $f$ は $x=a,b$ のどちらかで最小値である．
この性質に注目して二分探索のようなことをすると，幅が $L$ になって単調性が決定できない場合には，左半分または右半分のどちらかで単調性が決定できることが分かるので，単調列への分解は $O\left(\frac{N}{L}\log N\right)$ 回程度でできます．
