A. Ela Sorting Books
貪欲に作っていきます．
B. Ela’s Fitness and the Luxury Number
$n=\lfloor\sqrt{x}\rfloor$, $nm=x$ として，$n^2+2n+1 \leq n^2+3n$ から $n\leq x \leq n+2$ が分かります．
C. Ela and Crickets
それぞれのコマの $x,y$ 座標ともに偶奇が不変です．たいていはこれで必要十分条件になるのですが，初期位置が $4$ 隅のうち $3$ マスである場合などに $O(1)$ 通りしか動けないパターンがあります．
D. Ela and the Wiring Wizard
最終的にスタートとゴールを $1$ 本の辺で結ぶとしてよいです．経路上に重み $a,b$ の辺があるときコスト $\min(a,b)$ で重み $a$ の辺に置き換えられるからです．
よって，各辺に対して，その辺を $0,n-1$ 間の辺にするための最小操作回数を求められればよいです．
操作した辺に印をつけると，おおよそ $0, u, b, n-1$ を含む steiner tree の辺の個数程度のコストが必要であること，十分であることが分かります．
E. Ela Goes Hiking
自分が右端である場合を除き，初手で右移動を選択すると詰みです．最初に衝突する瞬間を考えると分かります．初手で左移動を選択し，うまいこと左側全員を吸収したあと右側とバトルということになります．
左側とのバトルでは，左移動を選択した人の直前の人が問題です．そこより左側はタイブレイクのルールの関係もあり必ずひとつのかたまりになってバトルすることが分かるので，左側の数え上げは適当な $2$ べきです．
右側との勝負で負ける場合，最終的に残るのが誰かを考えると，$i$ での答は $2i$ 以降での答を引くという形で書けます．よって後ろから順に計算し，suffix 側の累積和を持てばよいです．
F. Ela and Prime GCD
指数が大きい素因数が多いとつらそうです．例えば指数が $3$ の素数 $p$ があると，全体の半数以上の約数は $p^2$ で割れるのでそのような数を奇数番目に配置するしかなく，また隣接ペアのうち半数以上は $p$ の倍数になってしまいます．$p^4$ や $p^3q^3$ の形の倍数のときには不可能であることが分かります．
$p^3q^2$，$p^2q^2r^2$ などは自分は証明しなかったのですが，実験でこれもなさそうだとなりました．
結局，$(3,1,1,1,1,\ldots)$, $(2,2,1,1,1,1,\ldots)$, $(2,1,1,1,1,\ldots)$, $(1,1,1,1,\ldots)$ などの型に対応することが課題となります．
「$1$」を追加するタイプの議論ができればよさそうです．次の 2 種の構築を使いました．
- 長さが奇数のサイクルができているとき，新たに素数 $p,q$ を追加可能
- [a,b,c,d,e] から [pa,qb,pc,qd,pe][qa,pb,qc,pd,qe][a,pqb,c,pqd,e][pqa,b,pqc,d,pqe],q,pq,p を作る．
- $(3,1,1,1,1,\ldots)$ 型で，奇数番目が $p^2$ の倍数になっているとき素数 $q$ を追加可能
- [a,b,c,d,e,f,g,h] から [a,bq,c,dq,e,fq,g,hq],q,[aq,b,cq,d,eq,f,gq,h] を作る．これだと真ん中の接続がうまくいっていない．そこで列から $p$ であるところを探して $q$ をスワップすると上手くいく．$a,h$ は $p$ の倍数であることから分かる．
はじめ前者のルールだけで実装しようとしていましたが，$(3,1,1,\ldots)$ パターンはサイクルにするのが不可能だったのであわてて後者を足しました．
G. Ela Takes Dancing Class
かなり熱烈実装という感じではある．
まず不動の人については，数直線から除外して座標を振りなおしておきます．以後すべて，この振りなおした座標で考えます．ただしこの座標変換もまあまあ厄介で，私の実装も適当な log はついてしまっていますし，「$k$ 番目の取得」では除外した点も含めた $k$ 番目であるところもかなり厄介です．
まあそれは気合だということにして，あとは全員が動く点だとします．シミュレーションをします．先頭の人から最初の移動で飛び越える最後の人までの固まりを考えます．この固まりが，特に何もなければ全員 $1$ 回ずつ移動します．よって，
- 次の「固まりの増加」「クエリ時点」のうちどちらかまでシミュレーションを進める．
- 固まりを全員 $k$ 回ずつ移動（上の 2 種が起きない間）
というようなことをやっていけば，何らかの計算 $O(N+Q)$ 回でできることになります．
前者では固まり部分のシミュレーションを中途半端に進める必要がありますが，これは列を split して途中までに区間加算すればよいです．
結局何もかもが，区間定数加算と二分探索程度の機能を持った平衡二分木を使って丁寧に実装すれば $O((N+Q)\log^2N)$ 程度の実行時間でできることになります．
