A. Sonya and Queries
数ではなくその数の属するパターンを追加削除するとして数えればよいです．
B. Searching Rectangles
まず返り値が 1 となる区間をひとつ見つけます．
返り値が 2 であるような状態からはじめて，$4$ 辺境界について二分探索する形でできます．
返り値が 1 であるような区間が与えられれば，やはり $4$ 辺について二分探索することで長方形をひとつ見つけることができます．
ひとつめを見つければ，その上・下・左・右側のどれかの領域にふたつめがあってここからふたつめを発見できます．
「$4$ 辺境界に対する二分探索」というタイプの計算 $3$ 回で解けるので，全体では $12\log_2N$ 回程度で解けています．
C. Sonya and Problem Without a Legend
$O(N\log N)$ 時間で解けます．slope trick で解ける有名問題です．
参考：https://maspypy.com/slope-trick-2-%e5%95%8f%e9%a1%8c%e7%b7%a8#toc2
D. Animals and Puzzle
まず各 $(i,j)$ に対して，$(i,j)$ を左上隅とする最大正方形サイズを求めておきます．
これは降順に dp で計算できることは有名だと思います．
各クエリについては，二分探索で答を求めることを考えると，静的 $2$ 次元配列に対する矩形 max クエリができればよいと分かります．
私は，各軸にセグメント木・スパーステーブルをそれぞれ持たせることで，前計算・空間 $O(NM\log M)$，クエリ $O(\log N)$ 時間という実装をしました．解説では $2$ 次元スパーステーブルと言っていて，確かにそれでもメモリ制約は大丈夫なようです．
E. Sonya Partymaker
まず誤読に気を付けます．私は長く，毎秒どっちか向きに進む問題を考えてしまっていましたが，おそらく「最初に方向を選ぶ」「毎ターンその方向に移動」ということだと思います（同じ人が動く方向は一方向）．
次の二分探索判定問題を解けばよいです：各 $i$ に対して $[a_i-t,a_i]$ または $[a_i,a_i+t]$ という区間を置ける．円環全体を被覆できるか判定．
いったん円環要素を忘れて考えます．適当な $l,r$ があって，$[l,r]$ の被覆を目指す問題とします．
$i=0,1,2,\ldots$ 順に区間の置き方を決めていくのですが，次が成り立つとしてよいです：置いた区間全体が
$2$ 回に $1$ 回は，連結になっている（$i$ 個目，$i+1$ 個目を置いた直後に非連結になっていることはない）．$i$ 個目で連結性を崩したあと $j$ 個目で連結性を回復したとするとき，$i,\ldots,j-1$ 個目は右向き，$j$ 個目は左向きに置いていることになります．$j-i\geq 2$ のとき区間 $i+1$ 個目の向きを左向きに変えることで $i+1$ 時点で連結性があるようにできます．
これで，「$i$ 個目の区間を置いてその時点で連結になっている場合の右端」のような量を状態とする dp ができます．あとは円環要素に対応します．
適当に rotate して，円環の最大 gap が $(a[-1],a[0])=(a[N-1],a[N])$ であるとします．$t$ が十分大きくてこの gap が一方向だけで覆えるならば，すべての区間を同じ向きに置けばよいので，そうでないとします．
ここで円環を切り開けば，和集合が区間になるように区間の向きを決めることが必要になります．
あとはこの和集合の左端をどうするかですが，同じ状況下で，$0$ 番目または $1$ 番目の区間を左向きとしてよいことが最初の議論と同じように証明できるので，その $2$ 通りを計算すればよいです．
