单调队列

CF1904D

任意次选择一个子区间 $A[l\dots r]$，全部替换为子区间的最大值。判断是否可以通过若干次操作将数组 $A$ 变为数组 $B$。

对于每一个 $B[i]$，判断能否在 $A$ 中 找到一个相等的元素 $A[j]$，且 $i$ 和 $j$ 之间的所有 $k$ 都满足 $A[k] \le B[i]$，且 $B[k] \ge B[i]$。

这等价于 $A[j] \geqslant A[k]$，且 $A[j] \leqslant B[k]$。

因此需要维护一个递减的队列，如果 $A[j]<A[k]$，则淘汰 $A[j]$。同时，如果 $A[j]>B[k]$，需要淘汰队头的 $A[j]$。

std::vector<int> cnt(N, 0); 
std::deque<int> dq;
for (int i = 0; i < N; i++) {
    while (!dq.empty() && dq.back() < A[i]) {
        cnt[dq.back()]--;
        dq.pop_back();
    }
    if (dq.empty() || dq.back() > A[i]) {
        dq.push_back(A[i]);
        cnt[A[i]]++;
    }
    while (!dq.empty() && dq.front() > B[i]) {
        cnt[dq.front()]--;
        dq.pop_front();
    }
    if (cnt[B[i]] > 0) {
        match[i] = true;
    }
}