$D$：给你两个整数 $a, b$，问能否构造 $x, y$，使以下式子成立：

• $x \wedge y = a$
• $x + y = b$

思路：位运算的题目可以从每一位入手，分别考虑 $x,y$ 的第 $i$ 位 $x_i, y_i$

从表格中可以构造出新的一列 $(x_i+y_i) - (x_i \wedge y_i)$，记作 $c = b - a$，现在考虑能否构造出 $x, y$ 同时满足 $x \wedge y = a$ 和 $(x + y) - (x\wedge y) = c$，观察表格可以发现，只有当 $c_i = 0, a_i = 1$ 的情况下，无法构造出对应的 $x_i, y_i$。此外，还应满足 $c \ge a$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;

void solve() {
    int T;
    cin >> T;
    while (T --) {
        ll a, s;
        cin >> a >> s;
        s -= a;
        bool ok = s >= a;
        for (int i = 0; i < 60; i ++) {
            if ((s >> i & 1) == 0 and a >> i & 1) {
                ok = false;
                break;
            }
        }
        cout << (ok ? "Yes" : "No") << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

$E$：给你一个整数 $n$，并给你 $q$ 个区间 $[l, r]$，代表已知 $a_l + a_{l+1} + … + a_r$ 的和，问能否确定 $a_1 + a_2 + … + a_n$ 的和，只需回答能否确定

思路：用前缀和表示，$a_l + a_{l+1} + … + a_r = s_r - s_{l - 1}$，把每个 $s_i$ 看作一个节点，用边 $(s_i, s_j)$ 表示在已知 $s_i$ 或者 $s_j$ 的情况下，可以确定另一个的值是多少，这样每个区间相当于给两个节点连一条边，我们已知 $s_0 = 0$，只需看 $s_n$ 和 $s_0$ 是否连通

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 200010;

struct DSU {
    int n;
    vector<int> p, sz;

    DSU(int n) : n(n) {
        p.resize(n);
        sz.resize(n, 1);
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
    }

    int find(int x) {
        if (p[x] != x) 
            p[x] = find(p[x]);
        return p[x];
    }

    bool merge(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py)
            return false;
        n --;
        sz[py] += sz[px];
        p[px] = py;
        return true;
    }

    int size(int x) {
        return sz[find(x)];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    DSU dsu(n + 1);
    for (int i = 0; i < q; i ++) {
        int l, r;
        cin >> l >> r;
        dsu.merge(l - 1, r);
    }
    if (dsu.same(0, n))
        cout << "Yes\n";
    else
        cout << "No\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

$F$：给定 $n$ 个物品，每个物品的体积是 $1$，且有两个属性 $p, q$，当物品 $i$ 被选择时，满足 $p_j < p_i, q_j < q_i$ 的物品 $j$ 一定也要选上，问恰好选择体积为 $k$ 的方案个数

思路：把所有物品按照 $p$ 排序，之后只需考虑 $q$。难点在于怎么设计 $DP$，定义 $dp[i][j]$ 表示体积为 $i$ 时，未选择的物品的体积最小值是 $j$，状态转移的方程为：

• 不选当前物品，$ndp[i][min(q, j)] = ndp[i][min(q, j)] + dp[i][j]$
• 选当前物品，只能从 $j > q$ 的状态转移，$ndp[i][l] = ndp[i][l] + dp[i-1][l]$，其中 $l > q$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 998244353;
const int N = 200010;
# define ALL(A) A.begin(),A.end()

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n, 0);
    for (int i = 0; i < n; i ++)
        cin >> p[i];
    vector<int> q(n, 0);
    for (int i = 0; i < n; i ++)
        cin >> q[i];
    vector<array<int,2>> a;
    for (int i = 0; i < n; i ++)
        a.push_back({p[i], q[i]});
    // 一个人 i 如果被选，要满足 p_j < p_i 和 q_j < q_i 的人都被选
    sort(ALL(a));
    // dp[i][j] 选的体积为 i，且未选的最小的 q 是 j
    vector<vector<ll>> dp(k + 1, vector<ll>(n + 2));
    dp[0][n + 1] = 1;
    vector<int> cnt(n + 1, 0);
    for (auto& [p, q] : a) {
        vector<vector<ll>> ndp(k + 1, vector<ll>(n + 2));
        // 不选
        for (int j = 0; j <= k; j ++)
            for (int l = 0; l <= n + 1; l ++) {
                ndp[j][min(q, l)] += dp[j][l];
                ndp[j][min(q, l)] %= mod;
            }
        // 选
        for (int j = 1; j <= k; j ++)
            for (int l = q + 1; l <= n + 1; l ++) {
                ndp[j][l] += dp[j - 1][l];
                ndp[j][l] %= mod;
            }
        dp = ndp;
    }
    ll ans = accumulate(ALL(dp[k]), 0LL) % mod;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

$G$：给你 $n$ 个数 $a_1, a_2, …, a_n$，有 $q$ 个查询，对于每个查询，给定区间 $[l, r]$，需要判断 $\prod_{i=l}^ra_i$ 是否可以表示为一个数的三次方

思路：静态区间，用普通莫队离线查询，在添加或者删除一个元素后，考虑它的所有质因子，统计当前出现的每个质因子，是不是 $出现次数 \% 3 = 0$，可以用一个变量记录质因子中，$出现次数 \% 3 \neq 0$ 的个数，类似于在滑动窗口中可以做的优化，时间瓶颈在 $q$ 次查询，每次查询需要 $\sqrt{n}$ 次增加或者删除元素，每次增加或者删除元素时，需要枚举它的所有质因子，可以提前处理出来优化时间，在题目范围下，一个数的质因子个数不会很多，假设个数为 $m$，那么这个数 $x$ 至少是 $2 \times 3 \times … \times p_m > 2^m$，$m$ 是 $log(x)$ 量级，所以最终算法的复杂度分为两部分考虑：

• 预处理质因数 $O(n \times \sqrt{n})$，即 $2 \times 10^5 \times \sqrt{2 \times 10^5}$
• 莫队，$O(m \times \sqrt{n} \times{log(|a|)})$，即 $2 \times 10^5 \times \sqrt{2 \times 10^5} \times log(10^6)$，大概是 $10^8$ 数量级，勉强能过

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
# define ALL(A) A.begin(),A.end()

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    vector<array<int,3>> querys;
    for (int i = 0; i < q; i ++) {
        int l, r;
        cin >> l >> r;
        querys.push_back({l, r, i});
    }

    // 分解质因数
    auto div = [](int x) -> vector<array<int,2>> {
        vector<array<int,2>> res;
        for (int i = 2; i <= sqrt(x); i ++) {
            if (x % i == 0) {
                int s = 0;
                while (x % i == 0) {
                    x /= i;
                    s += 1;
                }
                res.push_back({i, s});
            }
        }
        if (x > 1)
            res.push_back({x, 1});
        return res;
    };

    vector<vector<array<int,2>>> primes(1000010);
    for (int i = 1; i <= n; i ++) {
        if (primes[a[i]].size())
            continue;
        else
            primes[a[i]] = div(a[i]);
    }

    // 原数组 a
    // 询问数组 querys, querys[i] = {l, r, id}

    vector<int> ans((int)querys.size(), 0);
    int len = sqrt(n);
    sort(querys.begin(), querys.end(), [&](auto& va, auto& vb) {
        int ia = va[0] / len, ib = vb[0] / len;
        if (ia != ib) 
            return ia < ib;
        if (ia & 1)
            return va[1] < vb[1];
        else
            return va[1] > vb[1];
    });

    // ------------------------
    // 修改的部分
    int nowAns = 0;
    // 不是 3 的倍数的质因数的个数
    int num = 0;
    vector<int> cnt(1000010, 0);
    // 增加一个元素 x 对结果的影响
    auto add = [&](int x) -> void {
        for (auto& [p, k] : primes[x]) {
            if (cnt[p] % 3 == 0)
                num --;
            cnt[p] += k;
            if (cnt[p] % 3 == 0)
                num ++;
        }
        nowAns = not num;
    };
    // 去掉一个元素 x 对结果的影响
    auto del = [&](int x) -> void {
        for (auto& [p, k] : primes[x]) {
            if (cnt[p] % 3 == 0)
                num --;
            cnt[p] -= k;
            if (cnt[p] % 3 == 0)
                num ++;
        }
        nowAns = not num;
    };
    // ------------------------

    for (int k = 0, i = 0, j = 1; k < querys.size(); k ++ )
    {
        auto& [l, r, id] = querys[k];
        while (i < r) add(a[ ++ i]);
        while (i > r) del(a[i -- ]);
        while (j < l) del(a[j ++ ]);
        while (j > l) add(a[ -- j]);
        ans[id] = nowAns;
    }

    for (int i = 0; i < ans.size(); i ++)
        cout << (ans[i] ? "Yes" : "No") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    T = 1;
    // cin >> T;
    while (T --)
        solve();
    return 0;
}