自动搬运

查看原文

来自洛谷，原作者为

	Engulf あまねく奇跡の始発点

搬运于2025-08-24 23:13:10，当前版本为作者最后更新于2025-07-31 22:22:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

:::warning[写在前面]{open}

本题解十分详细。按照正常思考顺序编写，可以跳转到自己卡壳的地方开始阅读。

只有绿色折叠框的代码 6 能够通过本题。 :::

subtask 1

暴力，枚举每个位置激活与否，若激活，激活了后面的哪个。

$\Theta(qk^n)$。

:::info[代码 1]

#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]

#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]

#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]

#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 的基础上改的。

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[后记 & 闲话]

为什么我要写这么详细的题解？

我个人是理解能力比较一般的人，每次看到模拟赛后贴出来的两三行题解，都得仔细研读，乃至去网上搜索更加详细的题解。这让我的改题十分痛苦，因为不能准确捕捉到写题解的人的意思。

我没有权利要求其他选手写出详细的题解，毕竟题解是选手花自己的时间分享自己的心得，而不是老师教导学生。但我想写详细的题解，真正能帮别人的学会这道题的题解，而不仅是自己的做题心得，而且详细的题解也能让我更好地梳理自己的思路，对题目有更深的认识。

居然每个部分都有代码？

这几个部分大致和出题人题解一样，我就是按着这几个部分一个部分一份代码写过来的。这也是正常、合理、科学的思考链条，按部就班有利于更好把握题目。

吐槽

这题花了我很多时间，毕竟每个部分我都去实现。但卡常花了我尤其久，有一天半左右了。总共提交了九十多发。卡常是真的恶心。题很好，就是卡常太恶心。

致谢

本题的出题人

助，是一位实力强大且思路清晰的选手。非常感谢。

闲话

洛谷更新的这个折叠框我非常喜欢。

这篇题解花了我很多时间，虽然这题是冷门题，看到的人也不多，但希望我的题解帮到了你。

这是我写过最久最长最详细的题解，27k+ 字。 :::