P11265 【模板】静态区间半群查询
题目描述
给定一个序列 $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$。
以上提到的两个函数实现如下：
```cpp
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 > 7;
return sd ^= sd
输出格式
设你某次查询得到的矩阵为 $res$，则这次查询的结果视为 $\sum_{0\le i,j\le1}(res_{i,j}\oplus kv_{i,j})$，其中 $\oplus$ 代表按位异或。输出所有 $m$ 个结果的异或值。
说明/提示
**本题采用捆绑测试。**
|Subtask 编号|$n$|$m$|$b$|分值|时限|
|-|-|-|-|-|-|
|0|$10^3$|$10^3$|$0$|$10$|$\texttt{1s}$|
|1|$5\times10^4$|$5\times10^4$|$0$|$10$|$\texttt{1s}$|
|2|$2\times10^5$|$2\times10^5$|$0$|$10$|$\texttt{1s}$|
|3|$10^6$|$2\times10^5$|$0$|$10$|$\texttt{3s}$|
|4|$2\times10^5$|$10^6$|$0$|$20$|$\texttt{3s}$|
|5|$10^6$|$10^6$|$0$|$10$|$\texttt{3s}$|
|6|$10^6$|$10^6$|$n-300$|$10$|$\texttt{3s}$|
|7|$10^6$|$10^6$|$n-500$|$10$|$\texttt{3s}$|
|8|$10^6$|$10^6$|$n-1000$|$10$|$\texttt{3s}$|
对于 $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++ 代码。
```cpp
#include
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 > 7;
return sd ^= sd > 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 > 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