P11265 【模板】静态区间半群查询
题目描述
给定一个序列 $a_1,a_2,\cdots,a_n$，其中的每个元素都是一个 $2\times2$ 的矩阵。你需要处理 $m$ 次查询，每次查询给定一个区间 $[l,r]$，你需要求出 $\prod_{i=l}^ra_i$，其中 $\times$ 符号代表 $(\min,+)$ 矩阵积。
**注意：本题时限极其宽松，主要作正确性测试使用和不准确的效率对比使用。请不要过分滥用本题评测资源。**
输入格式
无
输出格式
无
说明/提示
**本题采用捆绑测试。**
|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