Link & Luogu.
模拟赛题。感谢 @MiniLong 学长和 @carefree_Zhuang。
\(k\le 5\)，会影响到 \(h_i\) 的仅有它前 \(k\) 个位置，考虑状压。设 \(dp_{i,S}\) 表示对第 \(i\) 个位置，前 \(k\) 个位置中还未选定 \(j\) 的位置集合为 \(S\) 时，\(\max h\) 的最小值，转移时枚举 \(S\) 的子集 \(T\) 贡献到 \(dp_{i+1,f(S,T,op)}\)（\(op\) 表示是否激活 \(i\)）。对于每个询问的左端点分别 dp 即可。
给出方程：
发现这很矩乘。使用矩阵刻画转移，由于需要区间询问，把矩阵搬到线段树上做。直接合并转移矩阵复杂度太高，考虑用初始向量乘矩阵，单次询问可以做到 \(\mathcal{O}(4^k\log n)\)，总复杂度 \(\mathcal{O}(n8^k+q4^k\log n)\)。
考虑特殊性质 B：所有 \(x\) 相等。此时我们只关心 dp 值与 \(x\) 的大小关系，又 dp 值的合并只有 \(\min,\max\) 运算，于是将原矩阵换成 0/1 矩阵，表示矩阵上每个值是否 \(\le x\)，使用 std::bitset 存储，并用位运算刻画 \(\min,\max\)，复杂度 \(\mathcal{O}(\frac{n8^k+q4^k\log n}{\omega})\)。
受此启发，我们将询问按 \(x\) 升序排序。当 \(x=-\infin\) 时矩阵全为 \(0\)，我们仅需找出每个位置从 \(0\) 变成 \(1\) 的时间点，并在这个时间点的询问前加入线段树。
对于叶子节点，直接 dp 算出；对于非叶子节点，直接矩乘 pushup 复杂度爆炸，我们单独考察变化的位置对其父亲 \(u\) 的贡献：
不妨钦定变化的位置在 \(u\) 的左儿子 \(l\)，新增加的转移为 \(f\rightarrow g\)，则对于 \(u\)，新增加的转移必然是先在左儿子中 \(f\rightarrow g\) ，再通过右儿子 \(r\) 的某个转移 \(g\rightarrow h\)，形成一个新的转移 \(f\rightarrow h\)。右儿子情况类似。
维护出新增加的转移并在矩阵上修改，一路向上更新即可。时间复杂度？叶子节点的 dp 是 \(\mathcal{O}(n3^k)\) 的；全树仅 \(\mathcal{O}(n4^k)\) 个不同转移，对于一个转移，考虑它所在节点父亲新增的转移的复杂度为 \(\mathcal{O}(\frac{2^k}{\omega})\)；询问复杂度不变。总时间复杂度为 \(\mathcal{O}(n3^k+\frac{n8^k+q4^k\log n}{\omega})\)。
// godmoo's code
// P12151
#include <bits/stdc++.h>using namespace std;#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define mkp make_pair
#define lbd lower_bound
#define ubd upper_bound
#define IMX INT_MAX
#define LMX LLONG_MAX
#define mathmod(a) (((a) % MOD + MOD) % MOD)
#define mem(a, b) memset(a, b, sizeof(a))
#define cpy(a, b) memcpy(a, b, sizeof(b))
#define ckmx(a, b) (a = max(a, b))
#define ckmn(a, b) (a = min(a, b))
#define all(a) a.begin(), a.end()typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;const int N = 2e4 + 5;
const int M = 1e5 + 5;
const int V = 1e6 + 5, INF = 1e6;
const int ST = (1 << 5);int c, T, n, m, k, st, h[N], a[N], b[N], ans[M]; ll sb[N][ST];struct Task{int pos, f, g; // (pos - 1, f) -> (pos, g)Task() = default;Task(int pos, int f, int g): pos(pos), f(f), g(g){}
};
vector<Task> X[V];struct Query{int l, r, id;Query() = default;Query(int l, int r, int id): l(l), r(r), id(id){}
};
vector<Query> Q[V];typedef bitset<ST> Vector;
Vector operator -(const Vector& U, const Vector& V){ return (U | V) ^ V; } // 差集struct Matrix{Vector mat[ST];Vector row(int i) const{ return mat[i]; }auto get(int i, int j){ return mat[i][j]; }void clear(){ for(int i = 0; i < st; i++) mat[i].reset(); }
};
Vector operator*(const Vector& V, const Matrix& M){Vector R;for(int i = 0; i < st; i++) if(V[i]) R |= M.row(i);return R;
}namespace SegTree{int lf[N];Matrix pre[N << 2], nxt[N << 2];vector<pii> task[N << 2];void build(int u = 1, int l = 1, int r = n){if(l == r) return lf[l] = u, void();int m = l + r >> 1;build(u << 1, l, m), build(u << 1 | 1, m + 1, r);}Vector res;void _query(int u, int l, int r, int ql, int qr){if(ql <= l && r <= qr) return res = res * nxt[u], void();int m = l + r >> 1;if(ql <= m) _query(u << 1, l, m, ql, qr);if(qr > m) _query(u << 1 | 1, m + 1, r, ql, qr);}bool query(int l, int r){return res.reset(), res.set(0), _query(1, 1, n, l, r), res[0];}Vector tmp;void _upd(int u){for(auto [f, g] : task[u << 1]){tmp = nxt[u << 1 | 1].row(g) - nxt[u].row(f);for(int i = tmp._Find_first(); i < st; i = tmp._Find_next(i))nxt[u].get(f, i) = pre[u].get(i, f) = 1, task[u].eb(f, i);}task[u << 1].resize(0);for(auto [f, g] : task[u << 1 | 1]){tmp = pre[u << 1].row(f) - pre[u].row(g);for(int i = tmp._Find_first(); i < st; i = tmp._Find_next(i))pre[u].get(g, i) = nxt[u].get(i, g) = 1, task[u].eb(i, g);}task[u << 1 | 1].resize(0);}void upd(int u, int f, int g){if(nxt[u = lf[u]].get(f, g)) return;nxt[u].get(f, g) = pre[u].get(g, f) = 1, task[u].eb(f, g);u >>= 1; while(u){if(task[u << 1].empty() && task[u << 1 | 1].empty()) return;_upd(u), u >>= 1;}}void clear(int u = 1, int l = 1, int r = n){if(l > r) return;nxt[u].clear(), pre[u].clear(), task[u].resize(0);if(l == r) return;int m = l + r >> 1;clear(u << 1, l, m), clear(u << 1 | 1, m + 1, r);}
} using namespace SegTree;void init(){for(int i = 1; i <= n; i++) for(int S = 0; S < st; S++) sb[i][S] = 0;for(int x = 0; x <= INF; x++) X[x].resize(0), Q[x].resize(0);clear();
}void solve(){init();cin >> n >> m >> k, st = (1 << 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];for(int i = 1; i <= n; i++){for(int S = 0; S < st; S++) for(int j = 0; j < k; j++)if((S >> j & 1) && i - j - 1 > 0) sb[i][S] += b[i - j - 1];for(int S = 0; S < st; S++) for(int T = S; ; T = (T - 1) & S){ll x = h[i] - sb[i][T];if(x <= INF) X[max(x, 0ll)].eb(i, S, ((S ^ T) << 1) & (st - 1));if((x += a[i]) <= INF) X[max(x, 0ll)].eb(i, S, ((S ^ T) << 1) & (st - 1) | 1);if(!T) break;}}for(int i = 1, l, r, x; i <= m; i++) cin >> l >> r >> x, Q[x].eb(l, r, i);build();for(int x = 0; x <= INF; x++){ // T_max = 3for(auto [pos, f, g] : X[x]) upd(pos, f, g);for(auto [l, r, id] : Q[x]) ans[id] = query(l, r);}for(int i = 1; i <= m; i++) cout << (ans[i] ? "Yes\n" : "No\n");
}
int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);for(cin >> c >> T; T; T--) solve();cout << flush;return 0;
}