qoj8546题解补充

题解中第二种解法并没有具体解释是如何归纳的(害笔者想了两天两夜)，这里给一个证明。

考虑答案为(n,n)时，只需要全取max即可，接下来我们从n往n-1归纳，接下来所有位置初始都是取max的

情况1:a中的n和b中的n在同一个位置上，我们只需在这个位置上取min即可归纳到n-1，那么接下来我们钦定不会出现情况1。

情况2:不在一个位置上，我们钦定a中的n的位置<b中的n的位置。我们只需要在posa_n这个位置取min，如果n-1还是<b中的n的位置我们接着取min，否则我们交换a序列和b序列并保留之前所有位置的取min操作。

为什么操作2是对的呢？我们发现对于(x,y)向(x-1,y),(x,y-1),(x-1,y-1)移动的时候，x的位置和y的位置单调递增。而比x大的或比y大的地方都保有取min操作，所以答案必是(x,y)，证毕。所以并不会出现什么某个地方取min后会影响后面的答案的这种情况。