列の最大値は大きいほうから N 個の数:最下行の対角線以外のマスには、残りの数のうち大きいほうから N−1 個が入ります。左右を逆にしたので、大きいものほど左の列に入ります。大きいほうから N 個の数のうち、対角線にあるものは lN,lN−1,… と右下からつながっていて、その列の最大値になります。残りは最下行の左側の列に入り、どれもその列の最大値になります。よって S1 は常に上限の値になります。
したがって S1−S2=(大きいほうからN個の和)−(l1+⋯+lN) です。
li=iN とすると、S2 が下限になるので差は F です。そこから li を増やすと、増やした分だけ差が減ります。lN−1,lN−2,… の順に、li+1−1 を超えない範囲で必要な分だけ増やしていきます。全部を限界まで増やすと、対角線が大きいほうから N 個の数になって差は 0 になります。そのため、0 以上 F 以下のどの X でも作れます。
0 と 1 からなる長さ N の数列 A と、長さ M の数列 B が与えられます。N 行 M 列の配列 C を Ci,j=Ai+Bj で定めます。値が 2 のマスだけを考え、辺を共有するマスどうしをつないだときの連結成分のうち、最大のものの面積を求める問題です。値が 2 のマスがなければ 0 を出力します。
Union-Find(素集合データ構造、DSU)は、互いに交わらない集合の族を管理し、「2 つの集合を併合する」「2 つの要素が同じ集合にあるか判定する」をほぼ定数時間で行えるデータ構造です。各集合を根つき木で表し、経路圧縮と union by size(または union by rank)の両方を使うと、1 回の操作がならし O(α(n)) になります(α は逆アッカーマン関数)。片方だけでも、ならし O(logn) です。
Cartesian Tree は、数列の最小値を根にし、その左側と右側の部分列から左右の部分木を再帰的に作った二分木です(最大値を根にする流儀もあります)。添字について見ると二分探索木、値について見るとヒープになっています。スタックを使えば O(N) で構築できます。「区間を最小値で分割して再帰する」分割統治は、この木の上の再帰とみなせます。
d から要素を捨てるときは、その値が e の先頭と等しければ e からも捨てます。値しか比べていませんが、別の要素を取り違えることはありません。捨てる要素 x が e から消えているなら、x より後に x より大きい値が窓の中にあります。そのため e の先頭(窓の最大値)は x より大きく、等しくはなりません。最後の max(d) + k は、最終日まで配信する場合の値です。