【模板】静态区间半群查询

题目本身没啥意思，就是维护个矩阵区间乘法，上个线段树做完了。

我更想说说这个标题是啥意思。

半群说的是一个集合 S 和一种二元运算 \circ 。若运算 \circ 满足以下条件：

• \circ$ 具有封闭性，即 $\forall x,y\in S,x\circ y\in S
• \circ$ 满足结合律，即 $\forall x,y,z\in S,(x\circ y)\circ z=x\circ(y\circ z)

  则称 \left \langle S,\circ \right \rangle 为半群。

本题中 2\times2 矩阵和 (\min,+) 矩阵积运算就可以构成半群。

而线段树能维护的信息需要满足半群特性。线段树高速处理询问的实质是预处理出部分区间的答案，在查询时将询问区间拆分成若干段已经预处理的部分，然后拼接起来。将两段信息合并就需要其满足结合律。

题外话：ac-library 中的线段树中说其维护的线段树需满足幺半群性质。不过，考虑到幺元很容易构造（加一个 bool 变量就可以了），而且我实现的线段树并不需要幺元（代价是无法查询空区间），因此我说线段树维护的信息只需要半群即可。

#include <mrpython/typical_segment_tree.hpp> // see <https://github.com/Mr-Python-in-China/mp-oi-library/blob/main/library/mrpython/typical_segment_tree.hpp>
#include <cstdint>
#include <iostream>
using namespace std;
istream& fin = cin;
ostream& fout = cout;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
struct mat {
  int m[2][2];
  mat() {
    m[0][0] = m[1][1] = 0;
    m[1][0] = m[0][1] = 0x3f3f3f3f;
  }
  mat(int x, int y, int z, int w) {
    m[0][0] = x, m[0][1] = y, m[1][0] = z, m[1][1] = w;
  }
};
mat operator*(const mat& x, const mat& y) {
  return {min(x.m[0][0] + y.m[0][0], x.m[0][1] + y.m[1][0]),
          min(x.m[0][0] + y.m[0][1], x.m[0][1] + y.m[1][1]),
          min(x.m[1][0] + y.m[0][0], x.m[1][1] + y.m[1][0]),
          min(x.m[1][0] + y.m[0][1], x.m[1][1] + y.m[1][1])};
}
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.m[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.m[i][j] ^ kv[i][j];
    ans ^= tmp;
  }
} out;
int main(void) {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  size_t n, m;
  fin >> n >> m;
  rnd.init(), out.init();
  auto tree = [&]() {
    vector<mat> a(n);
    for (mat& i : a) rnd.genmat(i);
    return mrpython::typical_segment_tree<mat, multiplies<>>(a.begin(),
                                                             a.end());
  }();
  while (m--) {
    int l, r;
    rnd.genqry(l, r, n);
    --l;
    out.setres(tree.get(l, r));
  }
  fout << out.ans;
  return 0;
}