A. Portal
列を $2$ つ決めたときに，$O(H)$ で解きます．適当な累積和などを使えば，行 $x_1,x_2$ を使うときのコストは $f(x_1)+g(x_2)$ の形で書けます．
$x_2$ をインクリメントしながら，$x_1\leq x_2-4$ を満たす範囲での $f(x_1)$ の最小値を保持していけばよいです．
B. Mathematics Curriculum
最大値の位置で場合分けをすると dp の形になります．
具体的には答が dp[n][m][k] となるように dp テーブルを用意します．最大値の左右に $l,r$ 個の要素があるとして，$k$ 個の内訳を $k_l, k_r$ とすると，おおよそ $\mathrm{dp}[n][m][k] \leftarrow \binom{l+r}{l}\cdot \mathrm{dp}[l][m-1][k_1]\cdot \mathrm{dp}[r][m-1][k_2]$ のような遷移になります．
C. Train Maintenance
しきい値 $t$ を用意します．
$x+y>t$ のものは，個別に足します．$O(N/t)$ 個の区間加算になり，取得は最後に一度だけです．
$x+y<t$ のものは，$k=x+y$ を固定して同じ $k$ に対するデータをまとめて計算します．
$t=\sqrt{N}$ 程度にとれば $O(N^{1.5})$ 時間になります．
D. Subsequence
最小値の位置で切って再帰的に dp で答えを求めます．言い換えれば Cartesian Tree を作って木DPをします．
dp としては選んだ項数と，$ma_{b_{i}}+\sum_{i,j} f(b_i,b_j)$ の最大値を持たせます．$m$ は選んだ項数ではなく，最終的に選ぶ要素数（入力で与えられるやつ）としておくと，マージできます．
E. Railway Construction
まずはグラフパートを処理します．辺を張ったときに条件を満たしているかの判定を考えます．これは，最短路として使用可能な辺のみを残したDAGを作ったときに，$1$ 以外のすべての頂点について，「その頂点に向かう辺の始点が $2$ 種類以上」または「辺の始点が $1$ だけだが辺が $2$ 個以上」のどちらかを満たすというものです．
すると $Q=0$ の場合は次のようになります．まず dijkstra で既存の辺のみで DAG を作ります．入次数が $1$ の頂点 $v$ ごとに，高々ひとつの禁止頂点があります．$dist[i] < dist[v]$ かつ $i$ が禁止されていないような $i$ から辺を張るという方法のうち，最もコストが小さいものを使うという要領です．
あとはグラフを忘れてデータ構造パートです．各 $v$ について，使える最も安い $i$ を求めておきたいということになります．
まずクエリは逆順に処理します．こうすることで，コストの変更ではなく，安いコストの辺を追加する形にできます．また頂点番号は $dist$ 昇順などに並べて，入次数 $1$ のものは除いておきます．
おおよそ次のようになります．
- 列の各要素には色がついている．
- 列の suffix に対して，データ $(c,x)$ が追加されるイベントが来る．
- 各要素に対して，その位置にあるデータ $(c,x)$ であって $c$ が自身の色と異なるもののうち最もコストが小さいものを使用したときのコストを求める．
まず，色がない場合について考えます．各位置に対して最もコストが小さいデータだけを保持することになります．
そのような値はインデックスについて単調減少になり，定数区間を管理するテクニックで $O(Q)$ 回の区間更新に置き換えることができて解けます．
各要素の色を考慮すると，今度は各インデックスについて，top 2 min を保持するようにします．これも $O(Q)$ 回の区間更新に置き換えることができます．あとは各区間ごとに，その top 2 min の色とコストをもとに答を計算すればよく，これはできます．
F. Problems for Codeforces
自分は大変な多項式行列積で解いたんですが，包除原理でかなり綺麗に解けます．$N$ が奇数の場合が意外性がありました．
参考：https://codeforces.com/blog/entry/95477?#comment-845806
$M$ を $M-1$ に取り換えて $a_i+a_{i+1}\leq M$ として説明します．
$N$ が偶数
こちらは簡単だと思います．
インデックスの偶奇の一方を $M-a_i$ にとりかえると，$[0,M]$ に値を持つ列で，$\leq,\geq$ が交互に並ぶものを数えるという問題になります．$\geq$ という条件を包除原理で処理して，$<$ という条件いくつかと，条件が存在しないところいくつかという形にします．
条件が存在しないところで区切ると，$\leq,<$ でつながった列を数えることになります．長さ $2i$ のブロックの個数は適当な二項係数として数えられます．ブロックを並べた長さ $N$ の列を数えればよいのですが，円環要素を適切に処理する必要があります．
- 列のある場所に印をつける．印からはじめてブロックを置いて $k$ 個を置いて一周する．
- 円環を $k$ 個のブロックに切り分けて，そのうちひとつのブロックを選び，先頭に印をつける．
という個数が等しいことから，求めるべきは $N[x^N]\sum_kf(x)^k/k$ の形で書けることが分かります．これは fps log です．
$N$ が奇数
$M-a_i$ にとりかえるという処理はしません．要素を S, L の 2 種類に分けて考えます．S は，$2a_i\leq M$ を満たす $a_i$ で，L は $2a_i>M$ を満たす $a_i$ だとします．
すると，L 同士が隣接することはありません．S 同士が隣接する場所で区切ると，円環が SLSLS の形のブロックに分割されます．
そこで，$N$ が偶数の場合と同様に，SLSLS の形のブロックの数え上げを求めたあとで fps log という方針で答を求めることにします（同様に，といってもこの時点では包除原理は使っていません）．
そして，SLSLS の形のブロックを求めるために包除原理を使います．L に相当する要素を $M-x$ に取り換える処理を行います．「$2x\leq M$ である要素と $2x<M$ である要素の交互列であって $\leq, \geq$ が交互に並ぶもの」が数え上げ対象になります．そして，$\geq$ となっている場所に包除原理を適用して同じように処理します．
