求调

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 5e5 + 10;
const int maxm = 1000 + 10;
const int inf = 1e9;
int n, m, q, a[maxn], cnt[maxn], f[maxm][maxm][2], g[maxm][maxm][2];
void chmin(int& a, int b) { a = min(a, b); }
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], ++cnt[a[i]];
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    sort(a + 1, a + n + 1); n = unique(a + 1, a + n + 1) - a - 1;
    cin >> q;
    if (n >= 1000) {
        while (q--) cout << "No\n";
        return 0;
    }
    memset(f, 0x3f, sizeof(f)); memset(g, 0x3f, sizeof(g));
    f[1][n][0] = g[1][n][1];
    for (int len = n - 1; len >= 1; len--)
        for (int l = 1, r = len; r <= n; l++, r++) {
            int cur = cnt[a[l] - 1] + cnt[m] - cnt[a[r]] + 1;
            for (int k = 0; k < 2; k++)
                f[l][r][k] = min(f[l - 1][r][k] + cur * (a[l] - a[l - 1]), g[l][r + 1][k] + cur * (a[r + 1] - a[l])),
                g[l][r][k] = min(f[l - 1][r][k] + cur * (a[r] - a[l - 1]), g[l][r + 1][k] + cur * (a[r + 1] - a[r]));
        }
    while (q--) {
        int l, r, v; cin >> l >> r >> v;
        int ans = inf;
        if (r <= a[n]) {
            int id = lower_bound(a + 1, a + n + 1, r) - a;
            chmin(ans, f[id][id][0] + abs(l - a[1]) + (cnt[m] + 1) * abs(a[id] - r));
            chmin(ans, f[id][id][1] + abs(l - a[n]) + (cnt[m] + 1) * abs(a[id] - r));
        }
        if (a[1] <= r) {
            int id = upper_bound(a + 1, a + n + 1, r) - a - 1;
            chmin(ans, f[id][id][0] + abs(l - a[1]) + (cnt[m] + 1) * abs(a[id] - r));
            chmin(ans, f[id][id][1] + abs(l - a[n]) + (cnt[m] + 1) * abs(a[id] - r));
        }
        cout << (ans + cnt[m] <= v ? "Yes" : "No") << '\n';
    }
    return 0;
}