简单证明一下贪心思路:开始直接用完 m 个与操作,后面的全或是最优的。
首先,我们应该用尽量少的与操作,是显然的,也就是恰好 m 次。
其次,从与的本质考虑,无论什么区间与上区间 a 的结果一定不大于 a ,或则反之,任何区间或上 a 都不会小于 a 。
答案基本明了了,我们使用反证法,假设与不是前 m 个用完的,那么我们设最后一次与的区间是 i ,则这次操作之后的结果不大于 i ,但是如果我们把这个与操作扔到前面,换成或操作的话,一定是不小于 i 的,原操作不优,矛盾,得证。
所以先求出前 m 个区间的交,之后再求并集即可。