まず、\(LIS + LDS \le N+1\) が常に成り立ちます。これは、増加部分列と減少部分列が二つ以上の要素を共有することがないからです。

全探索を書くことで、\(LIS+LDS = N+1\) であるような順列の総数が \(\binom{2N-2}{N-1}\) であることを発見できます。Robinson–Schensted correspondence を知らなければ、驚いたかもしれません（私 ［訳注: antontrygubO_o 氏のこと］ もこの問題を解いていた時点では知らず、驚きました）。

順列を、\(N \times N\) のグリッド内の \(N\) 個のマスであって、どの二つも同じ行・列にないものの集合として解釈します。ここでは、増加部分列は右上に伸びていくマスの列であり、減少部分列は右下に伸びていくマスの列です。このような集合であって \(LDS + LIS = N+1\) であるものを、良い集合と呼びましょう。

ここで、隣接する列を切り分ける \(N-1\) 本の縦線と、隣接する行を切り分ける \(N-1\) 本の横線を考えます。これから、良い集合全体と、それらの \(2(N-1)\) 本の線から \(N-1\) 本を選ぶ方法全体の間の全単射を定義していきます。まず、\(i\) 番目の横線と \(j\) 番目の縦線の交点を \([i, j]\) と表記します。これをマスと混同してはいけません。\([i, j]\) はマス \((i, j)\) の右下の角です。

これらの線から、任意の \(N-1\) 本を選びます。これは縦線と横線を同数ずつ選ぶのと同等です。縦線と横線を \(K\) 本ずつ選んだとして、これらの線を青の線と呼びます。残りの \(2(N-1-K)\) 本は、黄色の線と呼びます。

（左から）\(i\) 本目の青い縦線と、（上から）\(i\) 本目の青い横線を考え、これらの交点を青で塗ります。

同様に、（右から）\(i\) 本目の黄色い縦線と、（上から）\(i\) 本目の黄色い横線を考え、これらの交点を黄色で塗ります。この時点では、マスでなく点を塗っていることに注意してください。

ここまでに \(N-1\) 個の点を塗っており、そのうち \(K\) 個は青で \(N-1-K\) 個は黄色です。これらがすべて異なる線上にあることは明らかです。また、青い点の全体が減少列をなし、黄色い点の全体が増加列をなすことも明らかです。

ここで、マスをいくつか選びましょう。すべての青い点 \([a, b]\) に対して、以下を行います。

• 点より右下の領域を見る。もしそこに黄色い点がなければ、マス \((a+1, b+1)\) を選び、青で塗る。

• 点より左上の領域を見る。もしそこに黄色い点がなければ、マス \((a, b)\) を選び、青で塗る。

また、すべての黄色い点 \([a, b]\) に対して、以下を行います。

• 点より右上の領域を見る。もしそこに青い点がなければ、マス \((a, b+1)\) を選び、黄色で塗る。

• 点より左下の領域を見る。もしそこに青い点がなければ、マス \((a+1, b)\) を選び、黄色で塗る。

ここで選んだマスについて、いくつかの簡単な主張を証明します。

• すべての青い点 \([a, b]\) について、マス \((a, b), (a+1, b+1)\) のうち少なくとも一方は選ばれている。実際、もしそうでなければ、左上領域と右下領域にともに黄色いマスが存在することになるが、黄色いマスは増加列をなすため、それは起こり得ない。

• 同様に、すべての黄色い点について、マス \((a, b+1), (a+1, b)\) のうち少なくとも一方は選ばれている。

• マス \((a, b)\) が選ばれたような青い点 \([a, b]\) は青い点全体の prefix をなし、マス \((a+1, b+1)\) が選ばれたような青い点は suffix をなす。

• マス \((a, b+1)\) が選ばれたような黄色い点 \([a, b]\) は黄色い点全体の prefix をなし、マス \((a+1, b)\) が選ばれたような黄色い点は suffix をなす。

ここで、どの青いマスもどの黄色いマスとも同じ行になく、同じ列にもないことを示しましょう。ある黄色いマスが、ある青いマスと同じ行にあると仮定します（列については、すべてが対称的になります）。マス \((x, y_1)\) が青、\((x, y_2)\) が黄色であるとします。まず、\(y_1 = y_2\) であることはありえません。なぜなら、もしそうだとすると、ある黄色い点とある青い点が同じ \(x\) 座標または同じ \(y\) 座標を持つことになりますが、それはありえない（マスを塗る起点となった点はこのマスの角、つまり、青なら右下か左上の角、黄色なら左下か右上の角でなければならない）からです。ここで、以下の二つの場合を考えます。

1. \(y_1<y_2\) の場合。もし青い点が \([x, y_1]\)、黄色い点が \([x-1, y_2]\) なら、\([x, y_2]\) は黄色で塗らなかったはずです。なぜなら、黄色い点の左下の領域に青い点があるからです。もし青い点が \([x-1, y_1-1]\) で黄色い点が \([x, y_2-1]\) なら、\([x-1, y_1-1]\) は青で塗らなかったはずです。なぜなら、青い点の右下の領域に黄色い点があるからです。

2. \(y_1>y_2\) の場合。同様の議論であり、繰り返しません。

これでマスが青と黄色で同時に塗られることはないことが証明されましたが、青で複数回（または黄色で複数回）塗られる可能性は残っています。

では、二つの異なる青いマスが同じ行・列にないことを示しましょう（黄色についても同様）。ある二つのマスが同じ行にあると仮定し、それらを \((x, y_1), (x, y_2)\) として \(y_1<y_2\) であるとします。すると、マス \((x, y_1)\) を \([x-1, y_1-1]\) から塗り、マス \((x, y_2)\) を \([x, y_2]\) から塗ったことになり、さらにこれらは「連続する」青い点であることになります。\(y_1 - 1 < y_2\) より、このことから \(y_1\) 番目の縦線に黄色い点があったことになります。しかし、これらのマスを塗ったという事実はそこに黄色い点はなかったことを意味し、矛盾します。

よって、青いマスが少なくとも \(K\) 個、黄色いマスが少なくとも \(N-1-K\) 個あり、それらは合計で \(N\) 個以下であることがわかりました（どの二つの異なる塗られたマスも行や列を共有しないため）。このとき、以下の二つの場合が考えられます。

• 塗られたマスの個数が \(N\) 個の場合。この場合、もうマスを塗る必要はありません。塗られたマスからなる集合が \(LIS+LDS = N+1\) を満たすことを示しましょう。\(LDS \ge K, LIS \ge N-K-1\) であることは明らかです。各点からマスを一つだけ塗ると、マスを \(N-1\) 個しか塗れないことに注意します。すると、一般性を失うことなく、ある青い点 \([a, b]\) から \((a-1, b-1)\) と \((a, b)\) の両方を塗ったとすることができます。このとき、\(LDS \ge K+1\) です。また、このことは、すべての黄色いマスがこの青い点の左下または右上にあり、マス \((a, b)\) を黄色いマスの増加列に含められることを意味します。よって、\(LIS \ge N-K\) となり、\(LIS + LDS \ge N+1\) です。

• 塗られたマスの個数が \(N-1\) 個の場合。この場合、塗られたマスがないような列と行に注目し、その交わるところのマスを \((x, y)\) とします。そして、このマスを \(N-1\) 個の塗られたマスとともに選びます。この集合も \(LIS + LDS = N+1\) を満たすことを示しましょう。しかしその前に、このケースをもう少し分析しましょう。「塗られたマスが \(N-1\) 個である」\(\implies\)「各点からマスを \(1\) つだけ塗った」に注意します。このとき、\(x-1\) 番目の縦線より上側（この線を含む）のすべての点について、（二つの選択肢のうち）上の方のマスを塗り、その線より下側のすべての点について、下の方のマスを塗ったことが容易にわかります。同様に、\(y-1\) 番目の横線より左側では、左の方のマスを塗り、右側では、右の方のマスを塗っています。すると、盤面の左上の方では左上のマスのみを塗っていることになり、それはこのプロセスを青い点についてのみ行っていたことを意味します。従って、\((x,y)\) から左上には青いマスのみがあり、（同様に）右下にも青いマスのみがあります。さらに同様にして、\((x,y)\) から右上や左下には黄色いマスのみがあります。このとき、マス \((x, y)\) を選ぶと確かに \(LIS\) と \(LDS\) がともに \(1\) 増加し、\(LIS + LDS = N+1\) となります。

ようやく、「線の選択 \(\to\) \(LIS + LDS = N+1\) であるような順列」の対応を完全に規定することができました。これが単射であることをここで証明するつもりはありません。読者に任せます。この解説の残りの部分では、これをどのように用いて問題の条件を満たす順列を数えるかを示します。

まず、これらの青・黄色の行を選んで \((pos, val)\) が塗られるようにする方法の個数を数える必要があります。このマスが青で塗られる回数を数えましょう。これは点 \([x-1, y-1]\) から何回塗られるでしょうか。

この青い点 \([x-1, y-1]\) の「番号」\(t\) をすべて試しましょう（最初の \(x-1\) 本の横線からちょうど \(t\) 本を選び、最初の \(y-1\) 本の縦線からちょうど \(t\) 本を選ぶことになり、その方法の個数は \(\binom{x-2}{t-1}\cdot \binom{y-2}{t-1}\) です）。このとき、黄色い横線を \(x-1-t\) 本、黄色い縦線を \(y-1-t\) 本選ぶことになります。\([x-1, y-1]\) の右上に黄色い点がないという条件は、\(N-1-K\) が \((x-1-t) + (y-1-t)\) 以下であることと同値です。よって、\(N-1-K \le x+y-2-2t \iff K\ge N+1+2t-x-y \implies \) 「青い線をあと \(N+1+t-x-y\) 本以上選ばなければならない」を得ます。青い線をあと \(t_1\) 本選ぶ方法の個数は \(\binom{N-x}{t_1}\cdot \binom{N-y}{t_1}\) です。求めたいものは、\(t_1\) が何らかの区間を動くときのこの値の和であり、それは累積和を用いて求められます。

同様に、このマスが点 \([x, y]\) から塗られる回数を数え、両方から塗られる回数を引きます（同じ考え方で計算します）。そして、マスが黄色で塗られる場合を同様に処理します。

最後に、マス \((x, y)\) が、黄色と青のマスが合計で \(N-1\) 個ある場合に「残りのマス」として塗られる回数を数えます。これも、やはり同様に処理できます。このマスより左上で選ぶ青い線の数 \(t\) をすべて試します。その際、マスの個数はすべて一意に特定でき、唯一の制約は、点 \([x-1, y-1], [x, y], [x-1, y], [x, y-1]\) が塗られてはならないことです（これを守れば、マス \((x, y)\) が塗られます）。これを、再び包除原理を用いて処理します。

合計計算量は \(O(N)\) です。

おまけ: この解説の誤植をすべて見つけてください。