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

ID: 10785

远端评测题

1000~3000ms

512MiB

尝试: 0

已通过: 0

难度: 5

上传者:

root

标签>

线段树

分块

题目描述

给定一个序列 $a_1,a_2,\cdots,a_n$ ，其中的每个元素都是一个 $2\times2$ 的矩阵。你需要处理 $m$ 次查询，每次查询给定一个区间 $[l,r]$ ，你需要求出 $\prod_{i=l}^ra_i$ ，其中 $\times$ 符号代表 $(\min,+)$ 矩阵积。

注意：本题时限极其宽松，主要作正确性测试使用和不准确的效率对比使用。请不要过分滥用本题评测资源。

输入格式

由于本题数据范围较大，测试点将在程序内生成。如果你不想看这一部分，我们也在题目最后提供了一份可以得到 $10\%$ 分数的 C++ 代码，可以直接拉到主函数改实现。

第一行四个非负整数 $n,m,sd,b$ ，代表序列长度，查询数目，你的随机数种子（64 位无符号二进制数），以及查询的随机参数。你需要将 $sd$ 重赋值为对其调用 splitmix64 得到的值。

第二行四个非负整数 $kv_{0,0},kv_{0,1},kv_{1,0},kv_{1,1}$ 。

接下来你需要调用 $n$ 次 rnd。设第 $i$ 次 rnd 的结果为 $(\overline{qwrxsytz})_{256}$ ，则 $a_i=\begin{pmatrix}z&y\\x&w\end{pmatrix}$ 。

接下来你需要生成 $m$ 次查询。对于每一次查询，先调用一次 rnd。若 $b>0$ 且结果为奇数，你调用一次 rnd 并记结果对 $n-b$ 取余的值 $c$ ，调用一次 rnd 并记结果对 $n-c$ 取模的值加一作为询问左端点 $l$ ，取 $l+c$ 作为询问右端点 $r$ ；否则，你调用两次 rnd 生成两个结果并将其分别对 $n$ 取余，取其中较小的余数加一作为询问左端点 $l$ ，较大的余数加一作为询问右端点 $r$ 。

以上提到的两个函数实现如下：

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;
}

输出格式

设你某次查询得到的矩阵为 $res$ ，则这次查询的结果视为 $\sum_{0\le i,j\le1}(res_{i,j}\oplus kv_{i,j})$ ，其中 $\oplus$ 代表按位异或。输出所有 $m$ 个结果的异或值。

输入数据 1

3 3 13148274 0
87 75 218 205

输出数据 1

输入数据 2

10 10 1145141919810 0
1 0 6 4

输出数据 2

输入数据 3

200000 1000000 61884 100
5 3 0 7

输出数据 3

45263464

提示

本题采用捆绑测试。

Subtask 编号	$n$	$m$	$b$	分值	时限
0	$10^3$		$0$	$10$	$\texttt{1s}$
1	$5\times10^4$
2	$2\times10^5$	$2\times10^5$
3	$10^6$	$2\times10^5$			$\texttt{3s}$
4	$2\times10^5$	$10^6$		$20$
5	$10^6$			$10$
6			$n-300$
7			$n-500$
8			$n-1000$

对于 $100\%$ 的数据， $1\le n,m\le 10^6$ ， $0\le b\le n-1$ ， $0\le sd\le2^{64}-1$ ， $0\le kv_{i,j}\le2\times10^8$ （ $0\le i,j\le1$ ）。

样例 1 解释：我们有 $a_1=\begin{pmatrix}202&50\\51&238\end{pmatrix}$ ， $a_2= \begin{pmatrix}167&154\\37&25\end{pmatrix}$ ， $a_3=\begin{pmatrix}164&145\\208&27\end{pmatrix}$ ，三组查询分别是 $[1,3]$ ， $[1,3]$ 和 $[1,2]$ 。前两组的答案矩阵均为 $\begin{pmatrix}251&102\\382&232\end{pmatrix}$ ，而第三组的答案矩阵为 $\begin{pmatrix}87&75\\218&205\end{pmatrix}$ 。根据题意模拟计算，最终输出为 $0$ 。

以下是一份可以得到 $10\%$ 分数的 C++ 代码。

#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;
  }
};
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];
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m, rnd.init(), out.init();
  for (int i = 1; i <= n; ++i) rnd.genmat(a[i]);
  // 你可以在这里进行你所需要的初始化。
  for (int l, r; m; --m) {
    rnd.genqry(l, r, n);
    out.setres(accumulate(a + l, a + r + 1, mat(), mul));
    // 你可以把上面这个 accumulate 改成自己的查询函数。
  }
  return cout << out.ans << endl, 0;
}

注意：观察代码可以发现，你实际上可以以任意顺序调用这 $m$ 次 setres。

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