Waku Waku Abyss Model Solution

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct MinDeque {
    int l = 0, r = 0;
    deque<pair<T, int>> dq;

    void push(T x) {
        while (!dq.empty() && x <= dq.back().first)
            dq.pop_back();
        dq.emplace_back(x, r++);
    }

    void pop() {
        assert(l < r);
        if (dq.front().second == l++)
            dq.pop_front();
    }

    T min() {
        assert(!dq.empty());
        return dq.front().first;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        for (int i=1; i<n; i++) {
            cin >> a[i];
            a[i] ^= a[i-1];
        }

        vector<int> dp(n, 1e9);
        dp[0] = 0;
        while (m--) {
            int s, e, l;
            cin >> s >> e >> l;
            s--, e--;

            vector<int> ndp(n);
            vector<MinDeque<int>> dq(1 << 5);
            for (int i=0; i<n; i++) {
                ndp[i] = dp[i];
                if (s <= i && i <= e) {
                    for (int mask=0; mask<1<<5; mask++)
                        if (!dq[mask].dq.empty())
                            ndp[i] = min(ndp[i], dq[mask].min() + (a[i] ^ mask) - 16);
                    dq[a[i]].push(dp[i]);
                }
                if (i >= l && s <= i - l && i - l <= e)
                    dq[a[i-l]].pop();
            }
            dp = move(ndp);
        }
        cout << dp[n-1] << "\n";
    }

    return 0;
}