CF edu 188 F 题解 - dk-qwq blog

F. Sum of Fractions #

题意#

每次操作可以使 $\frac x y$ ， $x \to x + 1$ 或者 $y \to y - 1$ （ $y > 1$ ）

$\mathrm{MSF}(b, k)$ 定义为：构造 $\left\{ \frac 1 {b_i} \right\}$ ，操作 $k$ 次，得到的最大和

给定数组 $a$ ，对于每个 $k_i$ ，求问 $\sum_{l = 1}^{n} \sum_{r = l}^{n} \mathrm{MSF} \left(a[l \dots r], k_i \right) \bmod 998\,244\,353$

题解#

首先考虑对于单个的 $\frac 1 v$ ，进行 $k$ 次操作

函数 $\frac {1 + k - x} {v - x}$ 显然是连续的，考虑调整法

解不等式 $\frac {1 + k} {v} < \frac {1 + k - 1} {v - 1}$ 得 $v < k + 1$ 即 $v \leq k$

故可以得到结论：

$v \leq k$ 的时候，让分母变为 $1$ ，再全部加到分子上即可
$v > k$ ，全部加到分子上

\Delta(v) = \begin{cases} k - v + 2, & v \leq k \\ \frac{k}{v}, & v > k \end{cases}

对于一个序列中，由 $\Delta$ 可以观察到一直使用最小的 $v$ 一定是最优的

统计序列中每个 $v$ 作为最小值占用多少个序列，使用单调栈解决即可

然后对 $v$ 排序，每次询问 $k_i$ 直接在序列 $v$ 上二分即可

总复杂度 $\Omicron (n \log n)$ ，提交记录

88 collapsed lines
#include <bits/stdc++.h>
#include <cassert>
#define debug(x) cout << #x << "= " << x << endl
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll qpow(ll x, ll k) {
    ll res = 1;
    while(k)  {
        if(k & 1ll) res = res * x % mod;
        k >>= 1, x = x * x % mod;
    }
    return res;
}
ll Inv(ll x) {
    return qpow(x, mod - 2);
}
const int N = 5e5 + 5;
int n, q;
ll a[N];
map<int, ll> _M; // v, cnt
map<int, ll> _ALL; // v, cnt
int m, v[N];
ll pre[N][2]; // for v <= k: -v / siz
ll suf[N]; // for v > k: (1/v)
void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<int> st(N);int len = 0;
    vector<int> l(n + 1), r(n + 1);
    a[0] = -1, st[len = 0] = 0;
    for(int i = 1; i <= n; i++) {
        while(a[st[len]] > a[i]) len--;
        l[i] = st[len] + 1;
        st[++len] = i;
    }
    a[n + 1] = -1, st[len = 0] = n + 1;
    for(int i = n; i >= 1; i--) {
        while(a[st[len]] >= a[i]) len--;
        r[i] = st[len] - 1;
        st[++len] = i;
    }
    for(int i = 1; i <= n; i++) {
        (_M[a[i]] += 1ll * (r[i] - i + 1) * (i - l[i] + 1) % mod) %= mod;
        (_ALL[a[i]] += 1ll * (n - i + 1) * (i - 1 + 1) % mod) %= mod;
    }
    for(auto [v, cnt]: _M) ::v[++m] = v;
    for(int i = 1; i <= m; i++) {
        pre[i][0] = 1ll * (-v[i]) * _M[v[i]] % mod;
        (pre[i][0] += pre[i - 1][0]) %= mod;
        (pre[i][0] += mod) %= mod;

        pre[i][1] = (pre[i - 1][1] + _M[v[i]]) % mod;
    }
    for(int i = m; i >= 1; i--) {
        // cout << v[i] << ' ' <<  _M[v[i]] << endl;
        suf[i] = Inv(v[i]) * _M[v[i]] % mod;
        (suf[i] += suf[i + 1]) %= mod;
    }

    ll ans = 0;
    for(int i = 1; i <= m; i++) {
        ans += Inv(v[i]) * (_ALL[v[i]] - _M[v[i]]) % mod;
        ans %= mod;
    }
    ans = (ans + mod) % mod;

    while(q--) {
        int k; cin >> k;
        int p = lower_bound(v + 1, v + 1 + m, k) - v;
        if(p > m) p = m;
        while(p >= 1 && v[p] > k) p--;
        ll res = 1ll * pre[p][1] * (k + 2) % mod + pre[p][0];
        res %= mod;
        (res += suf[p + 1] * (k + 1) % mod) %= mod;
        cout << (res + ans) % mod << endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    int T = 1;
    // cin >> T;
    while(T--) solve();
}

F. Sum of Fractions#

题意#

题解#

F. Sum of Fractions #