問題描述

你得到一個長度為 $n$ 的整數陣列

從左到右計算每個長度為 $k$ 的視窗的最小值

然後將這些最小值做 xor 運算（逐一累積後再輸出結果）

練習題

連結：https://cses.fi/problemset/task/3221

這題沒有辦法直接透過移除左元素跟新增右元素來完成，必須重新找最小值 $O(k)$，但這樣會超時，我們得想想別的方法

在同一方向上找極值，似乎可以使用單調性來解，但是要怎麼設計呢？

我們可以維護一個遞增的 deque，這樣第一個元素就是最小值，不過會有最小值已經在 window 外的情況

因此我們可以透過不斷對第一個元素看看他是否有超出去，有的話就 pop 掉

但這樣如果在 window 外元素的在 deque 中間呢？

其實並不影響，因為我們要的只是在 window 內最小值，那個元素等到之後他成為最小值時，就會被 pop 掉了

完整程式碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n, k;
    cin >> n >> k;
    ll x, a, b, c;
    cin >> x >> a >> b >> c;
    deque<pair<int, ll>> input;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (i != 0) {
            x = (a * x + b) % c;
        }
        while (!input.empty() && input.back().second >= x) {
            input.pop_back();
        }
        input.push_back({i, x});
        while (!input.empty() && input.front().first <= i - k) {
            input.pop_front();
        }
        if (i >= k - 1) ans ^= input.front().second;
    }
    cout << ans;
}