题解：P11265 【模板】静态区间半群查询

几个均可实现的做法。

比较广为人知的 O(n\log n)-O(1) 做法是猫树分治（二区间合并），即分治函数 S(l,r) 表示处理 [l,r] 之间的所有询问。

具体来说，设 mid 为区间 [l,r] 中点。只需要每次求出 [l,mid] 的后缀信息和 s_i 和 (mid,r] 的前缀信息和 t_i，对于每个跨过 mid 的询问 [L,R]，通过结合律合并 s_L 和 t_R；否则向两侧递归即可。这样做是预处理 O(n\log n)、查询 O(1) 的。一般来说做到线性空间需要将询问离线下来，而直接将分治树存下来能做到 O(n\log n) 空间的在线查询。

然后考虑序列分块。每 \log n 个位置分一块。预处理块内的前缀/后缀和，并对所有整块构成的序列做猫树分治，在本题的随机数据下期望是 O(n)-O(1) 的。但是如果询问在整块内部的话单次是 O(\log n) 的。

想要做到更快的话，可以将在一个整块内部的询问继续猫树分治下去。这样做的话在计算机的数据范围内可以认为是 O(n)-O(1) 的。

另一个可能更好写的随机数据期望 O(n)-O(1) 做法（这里我们认为 n,m 同阶）：

还是考虑序列分块。每 \sqrt n 个位置分一块。预处理块内的前缀/后缀和，以及任意两个整块之间所有块的信息和。查询跨过至少一个块的情况直接 O(1)，否则 O(\sqrt n) 暴力。

由于询问区间在一个整块内部的概率为 \frac{\sqrt n}{n}，于是暴力做的期望复杂度是 O(n) 的。

由于我是懒狗，只写了猫树分治的做法：

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool Mbe;

struct mat {
    int a[2][2];
    mat() {
        a[0][0] = a[1][1] = 0;
        a[1][0] = a[0][1] = 0x3f3f3f3f;
    }
    mat(int x, int y, int z, int w) {
        a[0][0] = x, a[0][1] = y, a[1][0] = z, a[1][1] = w;
    }
};

mat mul(const mat& x, const mat& y) {
    return {min(x.a[0][0] + y.a[0][0], x.a[0][1] + y.a[1][0]),
                    min(x.a[0][0] + y.a[0][1], x.a[0][1] + y.a[1][1]),
                    min(x.a[1][0] + y.a[0][0], x.a[1][1] + y.a[1][0]),
                    min(x.a[1][0] + y.a[0][1], x.a[1][1] + y.a[1][1])};
}

mat operator * (const mat &x, const mat &y) {
    return mul(x, y);
}

struct random {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    uint64_t rnd() {
        sd ^= sd << 13, sd ^= sd >> 7;
        return sd ^= sd << 17;
    }
    void init() { cin >> sd >> b, sd = splitmix64(sd); }
    void genmat(mat& res) {
        uint64_t val = rnd();
        for (int i : {0, 1})
            for (int j : {0, 1}) res.a[i][j] = val >> ((i << 1 | j) << 4) & 0xff;
    }
    void genqry(int& l, int& r, int n) {
        if ((rnd() & 1) && b) {
            int c = rnd() % (n - b);
            l = rnd() % (n - c) + 1, r = l + c;
        } else {
            l = rnd() % n + 1, r = rnd() % n + 1;
            if (l > r) swap(l, r);
        }
    }
    uint64_t sd;
    int b;
} rnd;

struct output {
    int ans, kv[2][2];
    void init() {
        for (int i : {0, 1})
            for (int j : {0, 1}) cin >> kv[i][j];
    }
    void setres(mat res) {
        int tmp = 0;
        for (int i : {0, 1})
            for (int j : {0, 1}) tmp += res.a[i][j] ^ kv[i][j];
        ans ^= tmp;
    }
} out;

constexpr int N = 1e6 + 9;

int n, m;
mat a[N];

namespace CatTree {

    struct Q {

        int l, r, i;

        Q () { }
        Q (int _l, int _r, int _i) : l(_l), r(_r), i(_i) { }

    };

    vector<Q> q;
    mat pr[N], sf[N], ans[N];

    void conq(int l, int r, vector<Q> q) {
        if (l == r) {
            for (Q p : q) {
                ans[p.i] = a[l];
            }
            return;
        }
        int mid = (l + r) >> 1;
        sf[mid] = a[mid];
        pr[mid + 1] = a[mid + 1];
        R (i, mid - 1, l) {
            sf[i] = a[i] * sf[i + 1];
        }
        F (i, mid + 2, r) {
            pr[i] = pr[i - 1] * a[i];
        }
        vector<Q> ql, qr;
        for (Q p : q) {
            int L = p.l, R = p.r, i = p.i;
            if (L <= mid && mid < R) {
                ans[i] = sf[L] * pr[R];
            } else if (L > mid) {
                qr.eb(p);
            } else {
                ql.eb(p);
            }
        }
        conq(l, mid, ql);
        conq(mid + 1, r, qr);
    }

    void i(int l, int r, int id) {
        q.eb(Q(l, r, id));
    }

    void c() {
        conq(1, n, q);
    }

}

void solve() {
    cin >> n >> m, rnd.init(), out.init();
    for (int i = 1; i <= n; ++i) rnd.genmat(a[i]);

    for (int l, r, i = 1; i <= m; i++) {
        rnd.genqry(l, r, n);
        CatTree::i(l, r, i);
        // out.setres(accumulate(a + l, a + r + 1, mat(), mul));    
    }
    CatTree::c();
    F (i, 1, m) {
        out.setres(CatTree::ans[i]);
    }
    cout << out.ans << endl;
}

bool Med;
int main() {
    // FIO("");
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
    int T = 1;
    // cin >> T;
    while (T--) solve();
    cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
    return 0;
}