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

· · 题解

简单的期望 \mathcal O(n) 做法。

首先按序列分块，分 \sqrt n 块。

然后处理 f_{i ,j} 表示 i , j 块间矩阵的积，这个部分是 \mathcal O(n) 的。

对于 x , y 不在同一块的情况，则我们处理散块的前缀，后缀也可以处理：f_i = a_{i + 1} f_{i + 1}，时间复杂度 \mathcal O(1)。

同一块的情况，则暴力。

在同一块内的概率为 \dfrac{1}{\sqrt n}，期望时间复杂度 \mathcal O(1)。

#include <bits/stdc++.h>
using namespace std;
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;
  }
  friend bool operator == (mat x, mat y){
    return x . a[0][0] == y . a[0][0] && x . a[0][1] == y . a[0][1] && x . a[1][1] == y . a[1][1] && x . a[1][0] == y . a[1][0];
  }
};
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])};
}
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, ans;
mat a[N] , res[N] , f[2002][2002];
int bl[N];
int tp[N] , ed[N];
mat s[2004][2004];
mat t[2004][2004];
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m, rnd.init(), out.init();
  const int B = sqrt(n + m);
  for (int i = 1; i <= n; ++i) rnd.genmat(a[i]) , bl[i] = i / B + 1;
  // 你可以在这里进行你所需要的初始化。
  mat p;
  for(int i = 1; i <= n; ++ i){
    if(res[bl[i]] == p){
        res[bl[i]] = a[i];
        tp[bl[i]] = i;
        ed[bl[i]] = i + B - 1;
        ed[bl[i]] = min(ed[bl[i]] , n);
    }
    else res[bl[i]] = mul(res[bl[i]] , a[i]); 
  }
  for(int i = 1; i <= n / B + 1; ++ i){
    f[i][i] = res[i];
      for(int j = i + 1; j <= n / B + 1; ++ j)
        f[i][j] = mul(f[i][j - 1] , res[j]);
  }
  vector<int> cnt(B + 2);    
  mat empty;
  for(int i = 1; i <= n; i ++){
    cnt[bl[i]] ++; 
    s[bl[i]][cnt[bl[i]]] = mul(s[bl[i]][cnt[bl[i]] - 1] , a[i]);
  }
  for(int i = n; i >= 1; i --){
    cnt[bl[i]] --; 
    t[bl[i]][cnt[bl[i]]] = mul(a[i] , t[bl[i]][cnt[bl[i]] + 1]);
  }
  for (int l, r; m; --m) {
    rnd.genqry(l, r, n);
    if(bl[r] == bl[l]){
        out.setres(accumulate(a + l, a + r + 1, mat(), mul));
        continue;
    }
    mat ans;
    if(l != tp[bl[l]])  
        ans = t[bl[l]][l - tp[bl[l]]] , l = ed[bl[l]] + 1;
    if(bl[l] == bl[r]){
        out . setres(mul(ans , s[bl[l]][r - tp[bl[l]] + 1]));
        continue;
    }
    int q = r;
    if(q != bl[r]) q = tp[bl[r]] - 1;
    ans = mul(ans , f[bl[l]][bl[q]]);
    if(r != bl[r]) ans = mul(ans ,  s[bl[r]][r - tp[bl[r]] + 1]);
    out.setres(ans);
    // 你可以把上面这个 accumulate 改成自己的查询函数。
  }
  return cout << out.ans << endl, 0;
}