给定\(n\)的排列\(P_n\), 构造\(A_n,B_n\)满足
- \(A_1<A_2<...<A_n\)
- \(B_1>B_2>...>B_n\)
- \(A_{P_1}+B_{P_1}<A_{P_2}+B_{P_2}<...<A_{P_n}+B_{P_n}\)
- \(1\leq n\leq 2\times 10^4\)
- \(1\leq A_i,B_i \leq 10^9\)
乍一看是挺吓人的，但是我们可以从简单的情况入手
要满足不等式3，我们不妨设\(A_1+B_1=A_2+B_2=...=A_n+B_n=X\)
此时我们只用考虑\(P_n\)了，要使得\(A_{P_1}+B_{P_1}<A_{P_2}+B_{P_2}<...<A_{P_n}+B_{P_n}\)，我们按照P的顺序设置一个增量，上式不就等价于\(X+W_{P_1}<X+W_{P_2}<...<X+W_{P_n}\)
W从0到n-1加到A上，A的初值的公差设为n，就好了！
真的是太美丽了，此题只应天上有，蒟蒻难有几回闻（悲