如果你WAon#6#7#8
查看原帖
如果你WAon#6#7#8
356117
落木之樱meow楼主2024/8/21 09:31

在单调队列这一部分有一几个等号需要注意。

问题出在第二个while的if里面.如果元素在滑动窗口左边就要跳过,但是如果条件是 mp[j].pos <= mp[i].pos - r 那么会把边界上的跳掉。

        if (mp[i].pos < l) continue;
        while (!q.empty() && mp[q.front()].pos < mp[i].pos - r) q.pop_front(); // 滑动左端点
        while (j < i && mp[j].pos <= mp[i].pos - l) { 
            if (mp[j].pos < mp[i].pos - r) {
                j++;
                continue;
            }
            while (!q.empty() && dp[q.back()] < dp[j]) q.pop_back(); // 滑动右端点
            q.push_back(j);
            j++;
        }

2024/8/21 09:31
加载中...