自动搬运

查看原文

来自洛谷，原作者为

	SafariMo Let's go on a safari.

搬运于2025-08-24 23:05:52，当前版本为作者最后更新于2024-11-20 21:13:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单的期望 $\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;
}