题解：P12151 【MX-X11-T5】「蓬莱人形 Round 1」俄罗斯方块
Engulf
·
·
题解
:::warning[写在前面]{open}
本题解十分详细。按照正常思考顺序编写，可以跳转到自己卡壳的地方开始阅读。
只有绿色折叠框的代码 6 能够通过本题。
:::
subtask 1
暴力，枚举每个位置激活与否，若激活，激活了后面的哪个。
:::info[代码 1]
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
const int N = 2e4 + 5;
int n, q, k;
int h[N], a[N], b[N];
int backup[N];
int dfs(int u, int l, int r, int x) {
if (u > r) {
return *max_element(h + l, h + 1 + r) <= x;
}
if (dfs(u + 1, l, r, x)) return true;
for (int j = u + 1; j <= min(u + k, r); j++) {
h[u] += a[u];
h[j] -= b[u];
if (dfs(u + 1, l, r, x)) return true;
h[u] -= a[u];
h[j] += b[u];
}
return false;
}
void subtask1() {
while (q--) {
int l, r, x;
cin >> l >> r >> x;
for (int i = l; i <= r; i++) h[i] = backup[i];
cout << (dfs(l, l, r, x) ? "Yes\n" : "No\n");
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int c, tt;
cin >> c >> tt;
while (tt--) {
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) cin >> h[i], backup[i] = h[i];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
subtask1();
}
return 0;
}
```
:::
代码 1 期望获得 $5$ 分，实际获得 $5$ 分。
### subtask 2 & 3
$k\le 5$，考虑状压 dp。
设 $f_{i, S}$ 表示：处理至点 $i$，往前 $k$ 个点（**包括点** $i$）的状态为 $S$，此时前 $i$ 个数的最大值 的最小值。
其中 $S$ 是一个二进制数，$S$ 的第 $t(0\le t <k)$ 位为 $1$ 表示点 $i - t$ **已激活**，**但还没有往后贡献**（对应题目中就是，激活了点 $p$，但还没往后选择点 $j$）。
转移的时候，枚举 $S$ 的子集 $T$，让 $T$ 中的点贡献给 $i + 1$，即让 $h_{i + 1}$ 减去 $T$ 中点的 $b$。
而点 $i + 1$ 有激活与不激活两种选项，分别写出转移：
- 不激活点 $i + 1$：
$$f_{i + 1, (S \oplus T) \ll 1} = \min\left(f_{i + 1, (S \oplus T) \ll 1}, \max\left(f_{i, S}, h_{i + 1} - \sum\limits_{x \in T}b_x\right)\right)$$
- 激活点 $i + 1$：
$$f_{i + 1, (S \oplus T) \ll 1 | 1} = \min\left(f_{i + 1, (S \oplus T) \ll 1 | 1}, \max\left(f_{i, S}, h_{i + 1} + a_{i + 1} - \sum\limits_{x \in T} b_x\right)\right)$$
其中 $S \oplus T$ 表示去掉了子集 $T$（贡献给了 $i + 1$），或上 $1$ 表示激活点 $i + 1$，因为只处理到 $i + 1$，肯定是无法往后贡献的。
边界条件：$f_{l, 0} = h_l,f_{l, 1} = h_l + a_l$。其他状态初始设置为 $+\infty$。
若 $f_{r, 0} \le x$（所有激活了的点都贡献了出去），答案为 `Yes`，否则为 `No`。
$\Theta(qn3^k)$。
:::info[代码 2]
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
const int N = 2e4 + 5;
const int inf = 0x3f3f3f3f;
int n, q, k;
int h[N], a[N], b[N];
int f[N][32];
void chkmin(int &x, int y) {x = min(x, y);}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc, tt;
cin >> tc >> tt;
while (tt--) {
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
while (q--) {
int l, r, x;
cin >> l >> r >> x;
for (int i = l; i <= r; i++)
for (int j = 0; j < (1 << k); j++)
f[i][j] = inf;
f[l][0] = h[l], f[l][1] = h[l] + a[l];
for (int i = l; i < r; i++) {
for (int j = 0; j < (1 << min(k, i - l + 1)); j++) {
chkmin(f[i + 1][j << 1 & 31], max(f[i][j], h[i + 1]));
chkmin(f[i + 1][(j << 1 | 1) & 31], max(f[i][j], h[i + 1] + a[i + 1]));
for (int s = j; s; s = (s - 1) & j) {
int d = 0;
for (int t = 0; t < min(k, i - l + 1); t++)
if (s >> t & 1) if (i - t >= l)
d += b[i - t];
chkmin(f[i + 1][(j ^ s) << 1 & 31], max(f[i][j], h[i + 1] - d));
chkmin(f[i + 1][((j ^ s) << 1 | 1) & 31], max(f[i][j], h[i + 1] + a[i + 1] - d));
}
}
}
cout << (f[r][0] <= x ? "Yes\n" : "No\n");
}
}
return 0;
}
```
:::
代码 2 期望获得 $25$ 分，实际获得 $15$ 分（这份代码没有特殊处理特殊性质 A，A 的话只要跑一遍全局的 dp 就行）。
### subtask 4 ~ 7
如何加速区间询问？
观察转移方程：
$$f_{i + 1, (S \oplus T) \ll 1} = \min\left(f_{i + 1, (S \oplus T) \ll 1}, \max\left(f_{i, S}, h_{i + 1} - \sum\limits_{x \in T}b_x\right)\right)$$
$$f_{i + 1, (S \oplus T) \ll 1 | 1} = \min\left(f_{i + 1, (S \oplus T) \ll 1 | 1}, \max\left(f_{i, S}, h_{i + 1} + a_{i + 1} - \sum\limits_{x \in T} b_x\right)\right)$$
可以发现它们的形式都类似这样：
$$f_{i + 1, U} = \min\left(f_{i + 1, U}, \max\left(f_{i, S}, v\right)\right)$$
由于 $\min$ 运算对 $\max$ 运算有分配律（反过来也成立哦），上式可以矩阵乘法加速，定义转移矩阵 $A_{S, U} = v$，那么 $f_{i + 1} = f_i \times A$。
进一步发现，每个 $i$ 对应的转移矩阵 $A$ 是一样的，问题转化成了求静态的区间矩阵乘积，使用线段树维护。
注意询问的时候，查到线段树上对应的某个区间的矩阵乘积，直接用答案向量 $f$ 去乘它，不要把一堆这些矩阵乘在一次，不然时间复杂度会多乘上一个 $2^k$。
$\Theta(n8^k + q4^k\log n)$。
:::info[代码 3]
```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
const int N = 2e4 + 5;
const int inf = 0x3f3f3f3f;
int n, q, k;
int h[N], a[N], b[N];
// int f[N][32];
void chkmin(int &x, int y) {x = min(x, y);}
using Matrix = vector<vector<int>>;
Matrix I() {Matrix I(1 << k, vector<int>(1 << k, inf)); for (int i = 0; i < I.size(); i++) I[i][i] = -inf; return I;}
Matrix operator*(const Matrix &a, const Matrix &b) {
Matrix c(1 << k, vector<int>(1 << k, inf));
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b[0].size(); j++)
for (int k = 0; k < b.size(); k++)
c[i][j] = min(c[i][j], max(a[i][k], b[k][j]));
return c;
}
Matrix tr[N << 2];
void build(int p, int l, int r) {
if (l == r) {
tr[p].assign(1 << k, vector<int>(1 << k, inf));
for (int j = 0; j < (1 << k); j++) {
chkmin(tr[p][j][j << 1 & (1 << k) - 1], h[l + 1]);
chkmin(tr[p][j][(j << 1 | 1) & (1 << k) - 1], h[l + 1] + a[l + 1]);
for (int s = j; s; s = (s - 1) & j) {
int d = 0;
bool valid = true;
for (int t = 0; t < k; t++)
if (s >> t & 1) {
if (l - t < 1) {
valid = false;
break;
}
d += b[l - t];
}
if (!valid) continue;
chkmin(tr[p][j][(j ^ s) << 1 & (1 << k) - 1], h[l + 1] - d);
chkmin(tr[p][j][((j ^ s) << 1 | 1) & (1 << k) - 1], h[l + 1] + a[l + 1] - d);
}
}
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
tr[p] = tr[p << 1] * tr[p << 1 | 1];
}
void query(int p, int l, int r, int L, int R, Matrix &f) {
if (L > R || r < L || l > R) return;
if (L <= l && r <= R) {f = f * tr[p]; return;}
int mid = l + r >> 1;
query(p << 1, l, mid, L, R, f);
query(p << 1 | 1, mid + 1, r, L, R, f);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc, tt;
cin >> tc >> tt;
while (tt--) {
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
build(1, 1, n - 1);
while (q--) {
int l, r, x;
cin >> l >> r >> x;
Matrix f(1, vector<int>(1 << k, inf));
f[0][0] = h[l], f[0][1] = h[l] + a[l];
// auto A = query(1, 1, n, l, r - 1);
query(1, 1, n - 1, l, r - 1, f);
cout << (f[0][0] <= x ? "Yes\n" : "No\n");
}
}
return 0;
}
```
:::
代码 3 期望得分 $70$ 分，实际得分 $55$ 分（常数太大）。
### subtask 8
观察特殊性质 B：所有 $x$ 均相等。
实际上我们只关心每个数相对 $x$ 的大小关系，不妨令 $\le x$ 的数为 $0$，$>x$ 的数为 $1$，把 $2^k \times 2^k$ 的矩阵改成 $2^k$ 个 `bitset`，每个 `bitset` $2^k$ 位。其他同上。
用 `bitset` 加速矩阵乘法，具体地，原本的矩阵乘法形如
$$c_{i, j} = \min_{k}\max(a_{i, k}, b_{k, j})$$
改成 $0/1$ 后可以用位运算
$$c_{i, j} = \text{and}_k(a_{i, k} \ \text{or} \ b_{k, j})$$
$j$ 这一维可以省略了，仅需枚举 $i$ 和 $k$。
- 若 $a_{i, k} = 1$，后面 $\max(a_{i, k}, b_{k, j})$，也就是 $a_{i, k}\ \text{or} \ b_{k, j}$ 一定为 $1$，前面对 $1$ 取 $\min$ 显然不会影响 $c_{i, j}$。
- 若 $a_{i, k} = 0$，它不会影响 $\max$，可以直接拿掉，
$$c_{i, j} = \text{and}_k b_{k, j}$$
既然用了 `bitset`，就直接 $c_i = c_i \ \text{and} \ b_i$ 即可，复杂度除以 $w$。
$\Theta\left(\dfrac{n8^k + q4^k \log n}{w}\right)$。
:::info[代码 4]
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
const int N = 2e4 + 5;
const ll inf = (1ll << 32) - 1;
int n, q, k, x;
int h[N], a[N], b[N];
// int f[N][32];
using Matrix = vector<bitset<32>>;
ostream& operator<<(ostream &os, const Matrix &b) {
for (int i = 0; i < b.size(); i++) {
os << b[i];
if (i != b.size() - 1)
os << "\n";
}
return os;
}
Matrix operator*(const Matrix &a, const Matrix &b) {
Matrix c(32, bitset<32>(inf));
for (int i = 0; i < a.size(); i++)
for (int k = 0; k < b.size(); k++)
if (!a[i][k])
c[i] &= b[k];
// for (int i = 0; i < a.size(); i++)
// for (int j = 0; j < b[0].size(); j++)
// for (int k = 0; k < b.size(); k++)
// c[i][j] = c[i][j] & (a[i][k] | b[k][j]);
return c;
}
Matrix tr[N << 2];
void build(int p, int l, int r) {
if (l == r) {
tr[p].assign(32, bitset<32>(inf));
for (int j = 0; j < (1 << k); j++) {
tr[p][j][j << 1 & 31] = (h[l + 1] > x);
tr[p][j][(j << 1 | 1) & 31] = (h[l + 1] + a[l + 1] > x);
for (int s = j; s; s = (s - 1) & j) {
int d = 0;
bool valid = true;
for (int t = 0; t < k; t++)
if (s >> t & 1) {
if (l - t < 1) {
valid = false;
break;
}
d += b[l - t];
}
if (!valid) continue;
tr[p][j][(j ^ s) << 1 & 31] = tr[p][j][(j ^ s) << 1 & 31] & (h[l + 1] - d > x);
tr[p][j][((j ^ s) << 1 | 1) & 31] = tr[p][j][((j ^ s) << 1 | 1) & 31] & (h[l + 1] + a[l + 1] - d > x);
}
}
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
tr[p] = tr[p << 1] * tr[p << 1 | 1];
}
void query(int p, int l, int r, int L, int R, Matrix &f) {
if (L > R || r < L || l > R) return;
if (L <= l && r <= R) {f = f * tr[p]; return;}
int mid = l + r >> 1;
query(p << 1, l, mid, L, R, f);
query(p << 1 | 1, mid + 1, r, L, R, f);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc, tt;
cin >> tc >> tt;
while (tt--) {
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
int l, r;
cin >> l >> r >> x;
build(1, 1, n - 1);
while (q--) {
Matrix f(32, bitset<32>(inf));
f[0][0] = (h[l] > x), f[0][1] = (h[l] + a[l] > x);
query(1, 1, n - 1, l, r - 1, f);
cout << (!f[0][0] ? "Yes\n" : "No\n");
if (q) cin >> l >> r >> x;
}
}
return 0;
}
```
:::
代码 4 期望得分 $15$ 分，实际得分 $10$ 分（常数太大）。
### subtask 9 & 10
考虑推广特殊性质 B。将询问离线，将所有询问和 $A_{S, U} = v$ 这样的修改，按照 $x$（对于修改，则是 $v$）从小到大排序，优先修改后查询。
初始时从小到大遍历询问和修改，如果是询问，正常查询即可。
如果是修改，发现修改仅仅是将线段树某个叶子节点的矩阵的第 $S$ 行 $U$ 列置 $0$，如果 pushup 的时候直接左儿子矩阵乘右儿子矩阵，复杂度爆炸。
我们只考虑哪些位置要重新更新。叶子节点直接更改。
接下来，令左儿子的矩阵是 $a$，右儿子的矩阵是 $b$，该节点的矩阵是 $c$。
$$c_{i, j} = \min_k\max(a_{i, k}, b_{k, j})$$
$$c_{i, j} = \text{and}_k(a_{i, k} \ \text{or} \ b_{k, j})$$
依次往上看，先看叶子节点的父亲 $u$，发现儿子在左子树还是右子树的情况不同，分类讨论：
- 若修改来自 $u$ 的左儿子，不妨假设修改是把 $a_{i, k}$ 置 $0$。
- 若 $b_{k, j} = 1$，$a_{i, k} \ \text{or} \ b_{k, j}$ 一定为 $1$，不会影响前面的 $\text{and}$。
- 也就是只有 $b_{k, j} = 0$ 的位置可能会影响 $c_{i, j}$，只要找 $b_k$ 所有 $0$ 的位置，把 $c_{i, j}$ 置 $0$ 即可。
- 若修改来自 $u$ 的右儿子，不妨假设修改是把 $b_{k, j}$ 置 $0$。
- 若 $a_{i, k} = 1$，$a_{i, k} \ \text{or} \ b_{k, j}$ 一定为 $1$，不会影响前面的 $\text{and}$。
- 也就是只有 $a_{i, k} = 0$ 的位置会影响 $c_{i, j}$，只要找所有第 $k$ 位是 $0$ 的 $a_{i}$，把 $c_{i, j}$ 置 $0$ 即可。
对于左儿子，我们知道 libstdc++ 为 bitset 提供了方便的 `_Find_first()` 和 `_Find_next(pos)` 成员函数，但这是找 $1$ 的，把 $b_k$ 取反找 $1$ 就等价于找 $0$ 了。
对于右儿子，发现跨了 `bitset`，有点棘手？记录转置矩阵 $A^T_{j, i} = A_{i, j}$，修改是同步的，只有在这一步，要找所有第 $k$ 位是 $0$ 的 $a_i$，只需要找 $a^T_{k}$ 所有的 $0$ 即可，同上取反找 $1$ 即可。
注意，一个 $c_{i, j}$ 被置 $0$ 后就不会再变回 $1$，要保证每次找的 $1$ 一共只被找 $1$ 次，可以使用一些位运算技巧。
:::info[技巧]
因为是实现细节，所以放在了折叠框里。
左右儿子情况类似，不妨只讨论左儿子。
我们要找到所有位置 $j$，使得取反后的 $b_{k, j} = 0$，且这个位置没被我们找过，这意味着 $c_{i, j}=1$。我们的处理把 $b$ 取反得到 $b'$，现在要找 $b_{k, j} = 1$ 且 $c_{i, j} = 1$ 的位置，直接令 $b_k \leftarrow b_k \ \text{and} \ c_i$ 即可。
右儿子就是把 $b_k$ 换成了 $a^T_k$。
:::
发现现在 $c_{i, j}$ 又有若干个置 $0$ 的修改，用 vector 存下这些修改，在父亲处继续修改即可。
每个点我们保证了只有一次 $1$ 变成 $0$，一共有 $\Theta(n4^k)$ 个这样的操作。复杂度可接受。
$\Theta\left(\dfrac{n8^k + q4^k \log n}{w}\right)$。
:::info[代码 5]
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
const int N = 2e4 + 5, M = 1e5 + 5;
const unsigned inf = ~0;
int n, m, k;
int h[N], a[N], b[N];
using Matrix = vector<bitset<32>>;
int ans[M];
struct Query {
int l, r, x, id;
int typ;
Query(int l, int r, int x, int id, int typ) : l(l), r(r), x(x), id(id), typ(typ) {}
bool operator<(const Query &b) const {return x != b.x ? x < b.x : typ < b.typ;}
};
vector<Query> q;
ostream& operator<<(ostream &os, const Matrix &b) {
for (int i = 0; i < b.size(); i++) {
os << b[i];
if (i != b.size() - 1)
os << "\n";
}
return os;
}
bitset<32> operator*(const bitset<32> &a, const Matrix &b) {
bitset<32> c(inf);
for (int k = 0; k < b.size(); k++)
if (!a[k])
c &= b[k];
return c;
}
// Matrix operator*(const Matrix &a, const Matrix &b) {
// Matrix c(32, bitset<32>(inf));
// for (int i = 0; i < a.size(); i++)
// for (int k = 0; k < b.size(); k++)
// if (!a[i][k])
// c[i] &= b[k];
// return c;
// }
Matrix tr[N << 2], tr2[N << 2];
vector<pii> add[N << 2];
void build(int p, int l, int r) {
tr[p].assign(32, bitset<32>(inf));
tr2[p].assign(32, bitset<32>(inf));
if (l == r) return;
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
}
void modify(int p, int l, int r, int x, int s, int t) {
if (l == r) {
tr[p][s][t] = 0;
tr2[p][t][s] = 0;
add[p].emplace_back(s, t);
return;
}
int mid = l + r >> 1;
if (x <= mid) {
modify(p << 1, l, mid, x, s, t);
for (auto [s, t]: add[p << 1]) {
auto rev = ~tr[p << 1 | 1][t];
rev &= tr[p][s];
for (int k = rev._Find_first(); k < 32; k = rev._Find_next(k)) {
tr[p][s][k] = tr2[p][k][s] = 0;
add[p].emplace_back(s, k);
}
}
add[p << 1].clear();
add[p << 1].shrink_to_fit();
} else {
modify(p << 1 | 1, mid + 1, r, x, s, t);
for (auto [s, t]: add[p << 1 | 1]) {
auto rev = ~tr2[p << 1][s];
rev &= tr2[p][t];
for (int i = rev._Find_first(); i < 32; i = rev._Find_next(i)) {
tr[p][i][t] = tr2[p][t][i] = 0;
add[p].emplace_back(i, t);
}
}
add[p << 1 | 1].clear();
add[p << 1 | 1].shrink_to_fit();
}
// if (corp != tr[p]) {
// debug("Let's check out the mergement of matrix %d\n", p);
// debug("the modify comes from %s, and s = %d, t = %d\n", lef ? "left" : "right", s, t);
// cerr << "left matrix: \n" << tr[p << 1] << "\n";
// cerr << "right matrix: \n" << tr[p << 1 | 1] << "\n";
// cerr << "correct matrix " << p << ":\n" << corp << "\n";
// cerr << "present matrix " << p << ": \n" << tr[p] << "\n\n";
// }
}
void query(int p, int l, int r, int L, int R, bitset<32> &f) {
if (L > R || r < L || l > R) return;
if (L <= l && r <= R) {f = f * tr[p]; return;}
int mid = l + r >> 1;
query(p << 1, l, mid, L, R, f);
query(p << 1 | 1, mid + 1, r, L, R, f);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc, tt;
cin >> tc >> tt;
while (tt--) {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
q.clear();
for (int i = 1, l, r, x; i <= m; i++) {
cin >> l >> r >> x;
q.emplace_back(l, r, x, i, 1);
}
for (int i = 1; i < n; i++)
for (int j = 0; j < (1 << k); j++) {
q.emplace_back(j, j << 1 & 31, h[i + 1], i, 0);
q.emplace_back(j, (j << 1 | 1) & 31, h[i + 1] + a[i + 1], i, 0);
for (int s = j; s; s = (s - 1) & j) {
int d = 0;
bool valid = true;
for (int t = 0; t < k; t++)
if (s >> t & 1) {
if (i - t < 1) {
valid = false;
break;
}
d += b[i - t];
}
if (!valid) continue;
q.emplace_back(j, (j ^ s) << 1 & 31, h[i + 1] - d, i, 0);
q.emplace_back(j, ((j ^ s) << 1 | 1) & 31, h[i + 1] + a[i + 1] - d, i, 0);
}
}
build(1, 1, n - 1);
sort(q.begin(), q.end());
for (auto [l, r, x, id, typ]: q) {
if (typ) {
// Matrix f(32, bitset<32>(inf));
// f[0][0] = h[l] > x, f[0][1] = h[l] + a[l] > x;
bitset<32> f(inf);
f[0] = h[l] > x, f[1] = h[l] + a[l] > x;
query(1, 1, n - 1, l, r - 1, f);
ans[id] = !f[0];
} else {
modify(1, 1, n - 1, id, l, r);
}
}
for (int i = 1; i <= m; i++)
cout << (ans[i] ? "Yes\n" : "No\n");
}
return 0;
}
```
:::
代码 5 期望得分 $100$，实际得分 $5$。
### 卡常
:::warning{open}
本题卡常严重。
:::
这部分更多算是我的一些碎碎念，感觉偏离了题解本身教授题目做法的宗旨，所以我放在了折叠框里。
如果你觉得阅读完上面的题解后，认为自己能够写出复杂度正确且常数较小的优秀做法，你可以不用打开折叠框。但如果你认为自己可能会被卡常，可以阅读一下，了解一些注意事项。
:::info[卡常]
从代码 3 开始就埋下伏笔了。
代码 5 的复杂度正确，但因为常数巨大只能获得 $5$ 分。仔细分析不难发现，代码 5 的常数巨大主要由两方面导致：
#### 实现本身的不够优。
##### 排序
排序是很难被注意到的一点。
我们将所有的询问和修改放在了一起，可以发现，极端情况下询问和修改的总数是 $Q = q + 2n3^k = 9.82 \times 10^6$，直接排序乘上 $20$ 多的 $\log$，不优。
降低排序的复杂度就考虑计数排序，$x_i$ 的值域上限是 $h + a \le 10^6 + 10^6 = 2\times 10^6$，下限是 $0$ 减去 $k$ 个最大的 $b$ 就是 $-5\times 10^6$。值域大小 $7 \times 10^6$，可以接受。
计数排序的时间复杂度是 $\Theta(Q)$，$Q$ 是询问和修改的总数。
##### 构造转移矩阵
如果你看了我的代码 5 的实现，会发现那是我直接在 dp 的基础上改的。
```cpp
q.emplace_back(j, (j ^ s) << 1 & 31, h[i + 1] - d, i, 0);
q.emplace_back(j, ((j ^ s) << 1 | 1) & 31, h[i + 1] + a[i + 1] - d, i, 0);
```
我直接把所有的修改拿出来排序。但修改有很多是打在了同一个位置的，因为一个 $j$ 对应了最多 $32$ 个状态，这里跟 dp 的时候不一样，dp 的时候没有什么 $\Theta\left(\dfrac{q4^k\log n}{w}\right)$ 的修改，只有 $\Theta(1)$ 的取 $\min$。这是非常严重的失误，显然只有最小的 $x$ 有用。$1$ 改成 $0$ 后不会再修改。这可以显著减少修改。
上面这两个是导致常数巨大的主要原因。但还是在一些数据上跑得慢，剩下的就是常规的卡常技巧。
#### 常规卡常
我做了包括但不限于下面的常规卡常：
- 快读快写；
- 少用 vector；
- 修改的时候，记录一下序列的第 $i$ 个对应线段树哪个节点，直接从底往上修改，就不用再递归去找叶子，没有修改直接退出；
- 全局 `bitset`。
:::
:::success[代码 6]
```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
namespace fastio{ // from MiniLong
#ifdef ONLINE_JUDGE
char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
#define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
#else
#define get() getchar()
#endif
template<typename T> inline void read(T &t){
T x = 0, f = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
t = x * f;
}
template<typename T, typename ... Args> inline void read(T &t, Args&... args){
read(t);
read(args...);
}
template<typename T> void write(T t){
if(t < 0) putchar('-'), t = -t;
if(t >= 10) write(t / 10);
putchar(t % 10 + '0');
}
template<typename T, typename ... Args> void write(T t, Args... args){
write(t), putchar(' '), write(args...);
}
template<typename T> void writeln(T t){
write(t);
puts("");
}
template<typename T> void writes(T t){
write(t), putchar(' ');
}
#undef get
};
using namespace fastio;
const int N = 2e4 + 5, M = 1e5 + 5, Q = 5e6;
const unsigned inf = ~0;
int n, m, k;
int h[N], a[N], b[N];
int ans[M];
struct Query {
int l, r, x, id;
int typ;
Query() {}
Query(int l, int r, int x, int id, int typ) : l(l), r(r), x(x), id(id), typ(typ) {}
bool operator<(const Query &b) const {return x != b.x ? x < b.x : typ < b.typ;}
} q[M + N * 486], qq[M + N * 486];
bitset<32> tr[N << 2][32], tr2[N << 2][32];
vector<pii> add[N << 2];
int reff[N];
void build(int p, int l, int r) {
for (int i = 0; i < 32; i++) {
tr[p][i].set();
tr2[p][i].set();
}
if (l == r) return reff[l] = p, void();
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
}
void modify(int x, int s, int t) {
int p = reff[x];
if (!tr[p][s][t]) return;
tr[p][s][t] = tr2[p][t][s] = 0;
add[p].emplace_back(s, t);
p >>= 1;
while (p) {
if (add[p << 1].empty() && add[p << 1 | 1].empty()) break;
for (auto [s, t]: add[p << 1]) {
auto rev = ~tr[p << 1 | 1][t] & tr[p][s];
for (int i = rev._Find_first(); i < (1 << k); i = rev._Find_next(i)) {
tr[p][s][i] = tr2[p][i][s] = 0;
add[p].emplace_back(s, i);
}
}
add[p << 1].clear();
for (auto [s, t]: add[p << 1 | 1]) {
auto rev = ~tr2[p << 1][s] & tr2[p][t];
for (int i = rev._Find_first(); i < (1 << k); i = rev._Find_next(i)) {
tr[p][i][t] = tr2[p][t][i] = 0;
add[p].emplace_back(i, t);
}
}
add[p << 1 | 1].clear();
p >>= 1;
}
}
bitset<32> f, c;
void query(int p, int l, int r, int L, int R) {
if (L > R || r < L || l > R) return;
if (L <= l && r <= R) {
c.set();
for (int i = 0; i < (1 << k); i++)
if (!f[i])
c &= tr[p][i];
f = c;
return;
}
int mid = l + r >> 1;
query(p << 1, l, mid, L, R);
query(p << 1 | 1, mid + 1, r, L, R);
}
int cnt[7000005];
int g[32];
int main() {
int tc, tt;
read(tc, tt);
int maxx = 0;
while (tt--) {
read(n, m, k);
for (int i = 1; i <= n; i++) read(h[i]);
for (int i = 1; i <= n; i++) read(a[i]);
for (int i = 1; i <= n; i++) read(b[i]);
for (int i = 1; i <= maxx; i++) cnt[i] = 0;
int lenq = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < (1 << k); j++) {
for (int t = 0; t < 32; t++)
g[t] = 2e9;
for (int s = j; ; s = (s - 1) & j) {
int d = 0;
bool valid = true;
for (int t = 0; t < k; t++)
if (s >> t & 1) {
if (i - t < 1) {
valid = false;
break;
}
d += b[i - t];
}
if (!valid) continue;
g[(j ^ s) << 1 & 31] = min(g[(j ^ s) << 1 & 31], h[i + 1] - d);
g[((j ^ s) << 1 | 1) & 31] = min(g[((j ^ s) << 1 | 1) & 31], h[i + 1] + a[i + 1] - d);
// q[++lenq] = {j, (j ^ s) << 1 & 31, h[i + 1] - d, i, 0}, maxx = max(maxx, h[i + 1] - d + Q);
// debug("[%d][%d] = %d\n", j, (j ^ s) << 1 & 31, h[i + 1] - d);
// q[++lenq] = {j, ((j ^ s) << 1 | 1) & 31, h[i + 1] + a[i + 1] - d, i, 0}, maxx = max(maxx, h[i + 1] + a[i + 1] - d + Q);
// debug("[%d][%d] = %d\n", j, ((j ^ s) << 1 | 1) & 31, h[i + 1] + a[i + 1] - d);
if (!s) break;
}
for (int t = 0; t < (1 << k); t++) {
if (g[t] == 2e9) continue;
q[++lenq] = {j, t, g[t], i, 0};
maxx = max(maxx, g[t] + Q);
}
}
for (int i = 1, l, r, x; i <= m; i++) {
read(l, r, x);
maxx = max(maxx, x + Q);
q[++lenq] = {l, r, x, i, 1};
}
build(1, 1, n - 1);
for (int i = 1; i <= lenq; i++)
cnt[q[i].x + Q]++;
for (int i = 1; i <= maxx; i++)
cnt[i] += cnt[i - 1];
for (int i = lenq; i >= 1; i--)
qq[cnt[q[i].x + Q]--] = q[i];
for (int i = 1; i <= lenq; i++) {
int l = qq[i].l, r = qq[i].r, x = qq[i].x, id = qq[i].id, typ = qq[i].typ;
if (typ) {
// Matrix f(32, bitset<32>(inf));
// f[0][0] = h[l] > x, f[0][1] = h[l] + a[l] > x;
f.set();
f[0] = h[l] > x, f[1] = h[l] + a[l] > x;
query(1, 1, n - 1, l, r - 1);
ans[id] = !f[0];
} else {
modify(id, l, r);
}
}
for (int i = 1; i <= m; i++)
puts(ans[i] ? "Yes" : "No");
}
return 0;
}
```
:::
代码 6 期望得分 $100$，实际得分 $100$。
代码 6 和正常编写的代码 5 相比重构太多，可读性比较差。
### 后记 & 闲话
:::info[后记 & 闲话]
#### 为什么我要写这么详细的题解？
我个人是理解能力比较一般的人，每次看到模拟赛后贴出来的两三行题解，都得仔细研读，乃至去网上搜索更加详细的题解。这让我的改题十分痛苦，因为不能准确捕捉到写题解的人的意思。
我没有权利要求其他选手写出详细的题解，毕竟题解是选手花自己的时间分享自己的心得，而不是老师教导学生。但我想写详细的题解，真正能帮别人的学会这道题的题解，而不仅是自己的做题心得，而且详细的题解也能让我更好地梳理自己的思路，对题目有更深的认识。
#### 居然每个部分都有代码？
这几个部分大致和出题人题解一样，我就是按着这几个部分一个部分一份代码写过来的。这也是正常、合理、科学的思考链条，按部就班有利于更好把握题目。
#### 吐槽
这题花了我很多时间，毕竟每个部分我都去实现。但卡常花了我尤其久，有一天半左右了。总共提交了九十多发。卡常是真的恶心。题很好，就是卡常太恶心。
#### 致谢
本题的出题人 @[MiniLong](https://www.luogu.com.cn/user/573341) 给予了我很多帮助，是一位实力强大且思路清晰的选手。非常感谢。
#### 闲话
洛谷更新的这个折叠框我非常喜欢。
这篇题解花了我很多时间，虽然这题是冷门题，看到的人也不多，但希望我的题解帮到了你。
这是我写过最久最长最详细的题解，27k+ 字。
:::