各問題

A - Max Add

f(a) = A_1 * k + A_2 * (k - 1) + ... + A_k + max(A_1...A_k) * kです。

最大値はk - 1までの最大値とA_kを比較すればよく、前半の部分は累積和の累積和を取っていけば求められます。

なにをうっかりしたのかintで定義してしまい1WA・・・。

B - Uniformly Distributed

i + jが同じマスは、どのような経路を通っても同じ歩数で到達するため、同じ色でなければなりません。もしこれが違うマスがすでにあれば構築不可です。以下、そのようなマスがないこととして考えます。

i + jが同じマスで、全てがすでにどちらか一方で塗られているマスについては、その1通りで動かすことはできません。

i + jが同じマスで、一部がすでにどちらか一方で塗られているマスについては、塗られていないマスも同じ色で塗らなければならないため、1通りしかありません。

i + jが同じマスで、全てがまだ塗られていないマスの場合、全てを赤で塗るか、全てを青で塗るかの2通りがあります。

これらは全て独立しているため、各i + jについて通りの数を数えてかけ合わせたものが答えです。

modを取り忘れて1WAしました。

C - Swaps 2

（想定解は転倒数のようです）

まず、端から貪欲に決めていって構いません。追い越しが発生すると、追い越されたものが戻るための手順を余計に発生させてしまうため単純に損です。

単純にループで探すのはもちろん間に合わないので、Aの各値にインデックス（以下0-indexed）をあらかじめ加算するということをします。これをしたあとの値を持つインデックスをmapで管理して、各B_iについてB_i + iの値を持つインデックスをそのmapから取ってくれば対象のAがもといた位置を得られます。ただし、他の数値が移動することによって少しずつ後ろにずれていくので、そのずれは遅延セグ木でどこまでがいくつずれたかを管理しておきます。