CF2064E Mycraft Sand Sort

Sol

首先 \(c\) 不能变，否则第一列就会改变。

然后注意到 \(i,j(i<j)\) 能交换当且仅当满足以下任意一条：

1. \(\displaystyle\max_{k=i+1}^{j-1}a_k<\min(a_i,a_j)\)
2. i+1=j

那么考虑从小到大做，每次把小的数删除，然后维护相邻同色数组成的连通块，每一轮一定能从同色连通块中选出一个数作为当前的方案，然后将大小减一。

Code

Link。