在单调队列这一部分有一几个等号需要注意。
问题出在第二个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++;
}