警示后人
查看原帖
警示后人
186472
AC_loveRealNewbie楼主2025/1/25 02:55

本题和 P6242 思路上基本相同,但代码实现上存在一定差异。如果直接照搬 P6242 的代码可能导致 WA。

存在差异的根本原因是:P6242 只有区间推平上界操作,而本题同时存在区间推平上界操作和区间填平下界操作。

由于本题存在区间填平下界操作,因此需要维护最小值和次小值。这里存在一个代码实现上的问题:当一个区间的最大值等于最小值 / 次小值时,修改这个区间的最大值的同时也会修改这个区间的最小值 / 次小值。

在 P6242 中,因为不需要维护最小值和次小值,我们不用担心在修改最大值时同步修改最小值 / 次小值的情况。但本题需要同时维护最大值次大值和最小值次小值。因此修改最大值时,需要判断最小值 / 次小值是否同时被修改;修改最小值时,需要判断最大值 / 次大值是否同时被修改。

另外需要注意的是,P6242 的懒标记与本题也略有不同。

P6242 的懒标记可以分为两种,一种是最大值的懒标记,另一种是非最大值的懒标记。

如果你用同样的思路来做这道题,将懒标记分为三种,最大值懒标记,最小值懒标记和其他值懒标记,可能会导致 WA。就算不 WA 可能写法也会很麻烦。

原因和刚才大同小异,诸位稍加思考就能想到。

一个好的解决方案是这样设计本题的懒标记:最大值懒标记,最小值懒标记,全局懒标记。当出现区间内所有数一起加 kk 这个操作时,在全局懒标记上加 kk,而不是像上面那样在三个懒标记那里分别加 kk。其他地方稍微调整一下细节即可。

2025/1/25 02:55
加载中...