Code: Sum of Fractions

O(N^4) ↕

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int solve(vector<int> &a, int k) {
    int n = a.size();
    mint ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            int mn = *min_element(a.begin() + i, a.begin() + j + 1);

            if(k >= mn) {
                ans += k - mn + 2;
            } else{
                ans += mint(1 + k)/mn;
            }

            for(int x = i; x <= j; x++) {
                ans += mint(1)/a[x];
            }
            ans -= mint(1)/mn;
        }
    }
    return ans.val();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> k(m);
    for (int i = 0; i < m; i++) {
        cin >> k[i];
        cout << solve(a, k[i]) << '\n';
    }
}

O(N^3 Log(N)) ↕

#include <atcoder/modint>
#include <atcoder/segtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int op(int a, int b) { return min(a, b); }

int e() { return 1e9; }

int solve(vector<int> &a, int k) {
    int n = a.size();

    vector<mint> pref(n);
    pref[0] = mint(1) / a[0];
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1] + mint(1) / a[i];
    }

    auto get_sum = [&](int l, int r) {
        if (l > r) {
            return mint(0);
        }
        return pref[r] - (l ? pref[l - 1] : 0);
    };

    segtree<int, op, e> st(n);
    for (int i = 0; i < n; i++) {
        st.set(i, a[i]);
    }

    mint ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // For atcoder's segtree, prod(l, r) returns min(l ... r - 1).
            // Hence we add +1 to make inclusive range.
            int mn = st.prod(i, j + 1);

            if (k >= mn) {
                ans += k - mn + 2;
            } else {
                ans += mint(1 + k) / mn;
            }

            ans += get_sum(i, j);
            ans -= mint(1) / mn;
        }
    }
    return ans.val();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> k(m);
    for (int i = 0; i < m; i++) {
        cin >> k[i];
        cout << solve(a, k[i]) << '\n';
    }
}

O(N^3) ↕

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int solve(vector<int> &a, int k) {
    int n = a.size();

    mint ans = 0;
    for (int i = 0; i < n; i++) {
        int mn = a[i];
        mint sum = 0;
        for (int j = i; j < n; j++) {
            mn = min(mn, a[j]);
            sum += mint(1) / a[j];

            if (k >= mn) {
                ans += k - mn + 2;
            } else {
                ans += mint(1 + k) / mn;
            }

            ans += sum - mint(1) / mn;
        }
    }
    return ans.val();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> k(m);
    for (int i = 0; i < m; i++) {
        cin >> k[i];
        cout << solve(a, k[i]) << '\n';
    }
}

O(N^2 Log(N)) ↕

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int solve(vector<int> &a, int k) {
    int n = a.size();
    mint ans = 0;

    set<pair<int, int>> store;
    for (int i = 0; i < n; i++) {
        store.insert({a[i], i});
    }

    // When 2 elements in a subarray compete for the minimum, the one with
    // smaller index wins. This way, the minimum element of any subarray is
    // unique.

    set<int> alive;
    for (auto ele : store) {
        int i = ele.second;
        int mn = ele.first;

        auto r_itr = alive.upper_bound(i);
        int R = n;
        if (r_itr != alive.end()) {
            R = *r_itr;
        }

        auto l_itr = alive.upper_bound(i);
        int L = -1;
        if (l_itr != alive.begin()) {
            l_itr--;
            L = *l_itr;
        }

        mint cnt = mint(i - L) * mint(R - i);

        // a[i] contributes to all subarray with left endpoint (L, i]
        // and right endpoint [i, R).
        if (k >= mn) {
            ans += cnt * (k - mn + 2);
        } else {
            ans += cnt * (mint(1 + k) / mn);
        }

        ans -= cnt * (mint(1) / mn);
        alive.insert(i);
    }

    // Remaining contribution : Sum of all elements in all subarrays.
    for (int i = 0; i < n; i++) {
        // a[i] will be present in all subarrays that start towards its left
        // and end towards its right.
        ans += mint(i + 1) * (n - i) * (mint(1) / a[i]);
    }

    return ans.val();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> k(m);
    for (int i = 0; i < m; i++) {
        cin >> k[i];
        cout << solve(a, k[i]) << '\n';
    }
}

O(N^2 Log(N)) Optimized ↕

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

void solve(vector<int> &a, vector<int> k_vec) {
    int n = a.size();
    int m = k_vec.size();

    vector<mint> fixed(m), variable(m);

    auto add_contribution = [&](vector<mint> &vec, int l, int r, mint val) {
        if (l < 0 || r >= m || l > r) {
            return;
        }
        for (int x = l; x <= r; x++) {
            vec[x] += val;
        }
    };

    set<pair<int, int>> store;
    for (int i = 0; i < n; i++) {
        store.insert({a[i], i});
    }

    // When 2 elements in a subarray compete for the minimum, the one with
    // smaller index wins. This way, the minimum element of any subarray is
    // unique.

    set<int> alive;
    for (auto ele : store) {
        int i = ele.second;
        int mn = ele.first;

        auto r_itr = alive.upper_bound(i);
        int R = n;
        if (r_itr != alive.end()) {
            R = *r_itr;
        }

        auto l_itr = alive.upper_bound(i);
        int L = -1;
        if (l_itr != alive.begin()) {
            l_itr--;
            L = *l_itr;
        }

        // a[i] contributes to all subarray with left endpoint (L, i]
        // and right endpoint [i, R).
        mint cnt = mint(i - L) * mint(R - i);

        // Original code block
        // if (k >= mn) {
        //     ans += cnt * (k - mn + 2);
        //     ans += cnt * k - cnt * mn + cnt * 2; // simplified version
        // } else {
        //     ans += cnt * (mint(1 + k) / mn);
        //     ans += cnt / mn + k * cnt / mn; // simplified version
        // }

        // Handle the case when k >= mn.
        int lb = lower_bound(k_vec.begin(), k_vec.end(), mn) - k_vec.begin();
        add_contribution(fixed, lb, m - 1, -cnt * mn + cnt * 2);
        add_contribution(variable, lb, m - 1, cnt);

        // Handle the case when k < mn.
        lb--;
        add_contribution(fixed, 0, lb, cnt / mn);
        add_contribution(variable, 0, lb, cnt / mn);

        // This component will contribute irrespective of the value of k.
        add_contribution(fixed, 0, m - 1, -mint(1) * cnt * (mint(1) / mn));
        alive.insert(i);
    }

    // Remaining contribution : Sum of all elements in all subarrays.
    for (int i = 0; i < n; i++) {
        // a[i] will be present in all subarrays that start towards its left
        // and end towards its right.
        //
        // This component will contribute irrespective of the value of k.
        add_contribution(fixed, 0, m - 1,
                         mint(i + 1) * (n - i) * (mint(1) / a[i]));
    }

    for (int i = 0; i < m; i++) {
        mint ans = fixed[i] + variable[i] * k_vec[i];
        cout << ans.val() << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

O(N Log(N)) ↕

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

void solve(vector<int> &a, vector<int> k_vec) {
    int n = a.size();
    int m = k_vec.size();

    vector<mint> fixed(m), variable(m);

    auto add_contribution = [&](vector<mint> &vec, int l, int r, mint val) {
        if (l < 0 || r >= m || l > r) {
            return;
        }
        // Maintain as a difference array to avoid O(m) time per update.
        vec[l] += val;
        if (r + 1 < m) {
            vec[r + 1] -= val;
        }
    };

    auto convert_to_prefix_sum = [&](vector<mint> &vec) {
        for (int i = 1; i < m; i++) {
            vec[i] += vec[i - 1];
        }
    };

    set<pair<int, int>> store;
    for (int i = 0; i < n; i++) {
        store.insert({a[i], i});
    }

    // When 2 elements in a subarray compete for the minimum, the one with
    // smaller index wins. This way, the minimum element of any subarray is
    // unique.

    set<int> alive;
    for (auto ele : store) {
        int i = ele.second;
        int mn = ele.first;

        auto r_itr = alive.upper_bound(i);
        int R = n;
        if (r_itr != alive.end()) {
            R = *r_itr;
        }

        auto l_itr = alive.upper_bound(i);
        int L = -1;
        if (l_itr != alive.begin()) {
            l_itr--;
            L = *l_itr;
        }

        // a[i] contributes to all subarray with left endpoint (L, i]
        // and right endpoint [i, R).
        mint cnt = mint(i - L) * mint(R - i);

        // Original code block
        // if (k >= mn) {
        //     ans += cnt * (k - mn + 2);
        //     ans += cnt * k - cnt * mn + cnt * 2; // simplified version
        // } else {
        //     ans += cnt * (mint(1 + k) / mn);
        //     ans += cnt / mn + k * cnt / mn; // simplified version
        // }

        // Handle the case when k >= mn.
        int lb = lower_bound(k_vec.begin(), k_vec.end(), mn) - k_vec.begin();
        add_contribution(fixed, lb, m - 1, -cnt * mn + cnt * 2);
        add_contribution(variable, lb, m - 1, cnt);

        // Handle the case when k < mn.
        lb--;
        add_contribution(fixed, 0, lb, cnt / mn);
        add_contribution(variable, 0, lb, cnt / mn);

        // This component will contribute irrespective of the value of k.
        add_contribution(fixed, 0, m - 1, -mint(1) * cnt * (mint(1) / mn));
        alive.insert(i);
    }

    // Remaining contribution : Sum of all elements in all subarrays.
    for (int i = 0; i < n; i++) {
        // a[i] will be present in all subarrays that start towards its left
        // and end towards its right.
        //
        // This component will contribute irrespective of the value of k.
        add_contribution(fixed, 0, m - 1,
                         mint(i + 1) * (n - i) * (mint(1) / a[i]));
    }

    // Now convert the difference array to prefix sum array to retrieve the
    // actual values.
    convert_to_prefix_sum(fixed);
    convert_to_prefix_sum(variable);

    for (int i = 0; i < m; i++) {
        mint ans = fixed[i] + variable[i] * k_vec[i];
        cout << ans.val() << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

Model solution : silent_wood ↕

#include <bits/stdc++.h>

constexpr int P = 998244353;

typedef long long ll;

int power(int x, int y = P - 2) {
    int ans = 1;
    while (y) {
        if (y & 1) {
            ans = (ll)ans * x % P;
        }
        x = (ll)x * x % P;
        y >>= 1;
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n), inv(n);
    std::vector<int> sinv(n + 1), sinvi(n + 1);
    int k = std::__lg(n);
    std::vector st(k + 1, std::vector<std::pair<int, int>>(n));
    ll s1 = 0, s2 = 0;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        inv[i] = power(a[i]);
        st[0][i] = std::make_pair(a[i], i);
        s1 += inv[i], s2 += (ll)inv[i] * i % P;
        sinv[i + 1] = s1 % P, sinvi[i + 1] = s2 % P;
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j + (1 << i) - 1 <= n; j++) {
            st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        }
    }
    auto qmin = [&](int l, int r) -> int {
        int k = std::__lg(r - l + 1);
        return std::min(st[k][l], st[k][r - (1 << k) + 1]).second;
    };
    std::vector<int> mul(n);
    ll base = 0;
    auto dfs = [&](auto &&self, int l, int r) -> void {
        int p = qmin(l, r);
        mul[p] = (ll)(p - l + 1) * (r - p + 1) % P;
        ll s1 = 0, s2 = 0;
        s1 += sinvi[p] - sinvi[l] + P;
        s1 += (ll)(P - l + 1) * (sinv[p] - sinv[l] + P);
        s2 += sinvi[p + 1] - sinvi[r + 1] + P;
        s2 += (ll)(r + 1) * (sinv[r + 1] - sinv[p + 1] + P);
        // for (int i = l; i < p; i++) s1 += (ll)(i - l + 1) * inv[i] % P;
        // for (int i = p + 1; i <= r; i++) s2 += (ll)(r - i + 1) * inv[i] % P;
        base += s1 % P * (r - p + 1) % P;
        base += s2 % P * (p - l + 1) % P;
        if (l < p)
            self(self, l, p - 1);
        if (p < r)
            self(self, p + 1, r);
    };
    dfs(dfs, 0, n - 1);
    base %= P;
    std::vector<std::tuple<int, int, int>> vec(n);
    for (int i = 0; i < n; i++) {
        vec[i] = std::make_tuple(a[i], inv[i], mul[i]);
    }
    std::sort(vec.begin(), vec.end());
    std::vector<int> f(n + 1), g1(n + 1), g2(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        auto [a, inv, mul] = vec[i];
        f[i] = (f[i + 1] + (ll)inv * mul) % P;
    }
    for (int i = 0; i < n; i++) {
        auto [a, inv, mul] = vec[i];
        g1[i + 1] = (g1[i] + (ll)mul * a) % P;
        g2[i + 1] = (g2[i] + mul) % P;
    }
    while (q--) {
        int x;
        std::cin >> x;
        ll ans = base;
        int p = std::lower_bound(vec.begin(), vec.end(),
                                 std::make_tuple(x + 2, 0, 0)) -
                vec.begin();
        ans += (ll)f[p] * (x + 1);
        ans += (ll)g2[p] * (x + 2);
        ans += P - g1[p];
        // for (int i = 0; i < n; i++) {
        //     int val;
        //     if (x + 2 <= a[i]) {
        //         // val = (ll)(1 + x) * inv[i] * mul[i];
        //         val = 0;
        //     }
        //     else {
        //         val = 2 + x - a[i];
        //     }
        //     ans += (ll)val * mul[i] % P;
        // }
        std::cout << (ans % P) << std::endl;
    }
    return 0;
}