Good Bye 2024: 2025 is NEAR A - E

2053A - Tender Carpenter

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int cnt = 0;
        for (int i = 1; i < n; i++) {
            int j = i - 1;
            cnt += (2 * a[i] > a[j] && 2 * a[j] > a[i]);
        }
        cout << (cnt > 0 ? "YES" : "NO") << endl;
    }

    return 0;
}

2053B - Outstanding Impressionist

只需关注满足 $l=r$ 的 pieces，因为它们只能在固定的位置。

设 $w_{i}$ 的范围是 $[l_{i},r_{i}]$，那么 $w_{i}$ 无解 $\iff$ 对于每个位置 $p\ (l_{i} \leqslant p \leqslant r_{j})$，都存在某个 pieces $j \neq i$ 只能在 $p$ 这个位置，即 $l_{j}=r_{j}=p$ $\iff$ 区间 $[l_{i},r_{i}]$ 恰有区间长度 $r_{i}-l_+1$ 这么多个 pieces （去重）满足 $l_{j}=r_{j}$。

特判 $l_{i}=r_{i}$ 的情形，只要有另一个 $j \neq i$ 满足 $l_{j}=r_{j}=l_{i}$ 就无解。

先预处理某个位置 $p$ 是否存在某个 pieces 满足 $l_{j}=r_{j}=p$。区间计数用前缀和实现。

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> l(n), r(n);
        vector<int> f(2 * n);
        for (int i = 0; i < n; i++) {
            cin >> l[i] >> r[i];
            l[i]--;

            if (l[i] + 1 == r[i]) {
                f[l[i]]++;
            }
        }

        vector<int> pre(2 * n + 1);
        for (int i = 0; i < 2 * n; i++) {
            pre[i + 1] = pre[i] + (f[i] > 0);
        }

        string ans(n, '1');
        for (int i = 0; i < n; i++) {
            int cnt = pre[r[i]] - pre[l[i]];
            if (cnt == r[i] - l[i] && l[i] + 1 != r[i] || l[i] + 1 == r[i] && f[l[i]] != 1) {
                ans[i] = '0';
            }
        }

        cout << ans << endl;
    }

    return 0;
}

2053C - Bewitching Stargazer

记所有区间的左端点之和为 sum，区间个数为 cnt。每次递归 cnt 乘 2。如果原先区间是 $[l,r]$，分两半后是 $[l,?],[m+1,r]$，左端点之和增加了 $m+1$，也就是增加了 $l+(m-l+1)$，这个 $m-l+1$ 对于所有的区间都是个定值，总共有 cnt 个区间，那左端点之和增加了 $\operatorname{sum}+\operatorname{cnt}\cdot(m-l+1)$。递归计算。

计算答案：如果区间长度是奇数，答案就需要增加 $m$ 之和，按刚才的思路 $m=l+(m-l)$，这里 $m-l$ 仍然为定值，所以答案需要增加 $\operatorname{sum}+\operatorname{cnt}\cdot(m-l)$，同样在递归时计算。

时间复杂度 $\operatorname{O}(\log n)$。

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        int l = 0, r = n - 1;
        ll res = 0, sum = 0, cnt = 1;
        while (l <= r && r - l + 1 >= k) {
            int m = l + r >> 1;
            if ((r - l + 1) % 2 == 0) {
                r = m;
            } else {
                res += sum + cnt * (m - l + 1);
                r = m - 1;
            }
            sum = 2 * sum + cnt * (m - l + 1);
            cnt <<= 1;
        }
        
        cout << res << endl;
    }

    return 0;
}

2053D - Refined Product Optimality

用调整法易见，如果 $a$ 升序，那么当且仅当 $b$ 也升序时最优。

希望每次调整 $a$ 之后，$a$ 仍然升序。题给每次修改 $a$ 是 $a_{i}:=a_{i}+1$，所以只需要修改最后一个等于 $a_{i}$ 的数，将其 $+ 1$，并计算答案的修改量。

时间复杂度 $\operatorname{O}(n+q\log n)$。

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

ll qpow(ll a, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll inv(ll n) {
    return qpow(n, mod - 2);
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, q;
        cin >> n >> q;

        vector a(2, vector<int>(n));
        for (int o = 0; o < 2; o++) {
            for (int i = 0; i < n; i++) {
                cin >> a[o][i];
            }
        }

        auto aa = a;
        sort(aa[0].begin(), aa[0].end());
        sort(aa[1].begin(), aa[1].end());

        ll res = 1;
        for (int i = 0; i < n; i++) {
            res = res * min(aa[0][i], aa[1][i]) % mod;
        }

        cout << res << " ";
        while (q--) {
            int o, i;
            cin >> o >> i;
            o--, i--;

            int p = upper_bound(aa[o].begin(), aa[o].end(), a[o][i]) - aa[o].begin() - 1;
            res = res * inv(min(aa[o][p], aa[!o][p])) % mod;
            aa[o][p]++;
            a[o][i]++;
            res = res * min(aa[o][p], aa[!o][p]) % mod;

            cout << res << " ";
        }
        cout << endl;
    }

    return 0;
}

2053E - Resourceful Caterpillar Sequence

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> E(n);
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            E[u].push_back(v);
            E[v].push_back(u);
        }

        vector<int> op(n);
        for (int u = 0; u < n; u++) {
            op[u] = E[u].size() == 1;
        }
        for (int u = 0; u < n; u++) {
            if (op[u] == 1) continue;
            for (auto v : E[u]) {
                if (op[v] == 1) {
                    op[u] = 2;
                }
            }
        }

        int sum[3]{};
        for (int u = 0; u < n; u++) {
            sum[op[u]]++;
        }

        ll res = 0;
        vector<int> dp(n);
        auto dfs = [&](this auto&& self, int u, int p) -> void {
            if (op[u] == 0) dp[u] = 1;
            for (auto v : E[u]) {
                if (v == p) continue;
                self(v, u);
                dp[u] += dp[v];
            }

            if (op[u] != 2) return;

            ll sum1 = 0, sum2 = 0;
            for (auto v : E[u]) {
                int t;  // Change-Root dp
                if (v == p) {
                    t = sum[0] - dp[u];
                } else {
                    t = dp[v];
                }
                res -= 1LL * t * (op[v] != 1);
                sum1 += t;
                sum2 += (op[v] != 1);
            }
            res += 1LL * sum1 * sum2;
        };
        dfs(0, -1);

        res += 1LL * sum[1] * (n - sum[1]);
        cout << res << endl;
    }

    return 0;
}