Educational Codeforces Round 29 F. Almost Permutation

想定解はフローだが、離散凸解析をちょっと知っていると、目的関数がM凸なので、交換を繰り返すと解けることが分かる。

実際、Benqは本番これで通しているらしい

これを証明する。

問題文中で定義されている目的関数をfとする。これがM凸であることを示す。

まずfの定義域である、実行可能解の集合Sが整基集合（とりあえずM凸関数のステートメントが成立するような集合と考えていい）であることを示す。

↑ノリでm+1にしたけどmでよかったな

これはかなり雑、というかこの書き方だと、「対称性からy + e_i - e_jも実行可能解」が成立してないけど、1..nを頂点としたグラフ（辺は、数列の各要素kに関してL[k]からR[k]までの全てのペアに張る）上のpathをイメージするとできることは明らか

これさえ証明しておくと、M凸なのは2次関数の和だからかなり自明

実際これで通る。

https://codeforces.com/contest/863/submission/86645365

多分最悪計算量はO(N^4logN)とか（は？）

な気がする