类似这种hack:
9 2
0 5 10 0 0 0 0 0 0
1 1 3 5
2 1 3 5
正确输出:
2
这类数据可以卡掉一定的边界情况未处理好的问题,如第三篇题解能被这个数据卡掉。
如果在整个块进行修改时判断条件为 2×x>区间最大值,且未进行倒序枚举,会出现 0 合并到 x 的并查集,x 合并到 2×x 的并查集的情况,第三篇题解的错误也错在这里。
错误输出为:
3
构造大数据也很简单,只需要在一个块里控制一个偶数最大值,一个最大值的一半和一个 0,然后对整个区间做 1 操作, x 值为最大值的一半即可