题解：AT_abc292_h [ABC292Ex] Rating Estimator

endswitch · 2024-10-08 16:40:29 · 题解

首先可以把式子转换成 pre_k - k\times B \ge 0 的形式，放进线段树里面，此时对于原序列的单点修改转换成后缀修改。

下面将 pre_k - k\times B \ge 0 称为偏差值。

但是如果此时要查大于等于 0 的数的下标是 O(n) 的，因为其不满足单调性，无法二分。

此时有一个套路，对于一段原本不满足单调性的前缀取 \max，这个前缀 \max 序列便满足单调性了。

于是可以线段树二分找到第一个下标 pos 满足第 pos 个偏差值大于等于 0。

对于原序列，额外用一个树状数组维护动态前缀和。

写得有点丑，是 O(q\log^2n) 的。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 5; 
int n, B, Q, c, x, a[N], pre[N];

namespace SGT {
    #define mid (L + R) >> 1
    #define son p, L, R
    #define lson ls(p), L, (L + R) >> 1
    #define rson rs(p), ((L + R) >> 1) + 1, R

    struct Node {
        int mx, pls;
    } t[N << 2];

    inline int ls(int p) {
        return p << 1;
    }

    inline int rs(int p) {
        return p << 1 | 1;
    }

    inline void psup(int p) {
        t[p].mx = max(t[ls(p)].mx, t[rs(p)].mx);

        return ;
    }

    inline void modify(int x, int k, int p = 1, int L = 1, int R = n) {
        if(L == R) {
            t[p].mx = k;

            return ;
        }

        if(x <= mid) modify(x, k, lson);
        else modify(x, k, rson);

        psup(p);
    }

    inline void work(int p, int L, int R, int k) {
        t[p].mx += k;
        t[p].pls += k;

        return ;
    }

    inline void psd(int p, int L, int R) {
        if(! t[p].pls) return ;

        work(lson, t[p].pls), work(rson, t[p].pls);

        t[p].pls = 0;

        return ; 
    }

    inline void add(int l, int r, int k, int p = 1, int L = 1, int R = n) {
        if(l <= L && R <= r) {
            work(son, k);

            return ;
        }

        psd(son);

        if(l <= mid) add(l, r, k, lson);
        if(r > mid) add(l, r, k, rson);

        psup(p);

        return ;
    }

    inline int ask(int l, int r, int p = 1, int L = 1, int R = n) {
        int res = -1e18;

        if(l <= L && R <= r) return t[p].mx;

        psd(son);

        if(l <= mid) res = max(res, ask(l, r, lson));
        if(r > mid) res = max(res, ask(l, r, rson));

        return res;
    }

    inline int binary() {
        int l = 1, r = n, ans = n;

        while(l <= r) {
            int Mid = (l + r) >> 1;

            if(ask(1, Mid) >= 0) ans = Mid, r = Mid - 1;
            else l = Mid + 1;
        }

        return ans;
    }

    #undef mid
    #undef son
    #undef lson
    #undef rson
}

using namespace SGT;

namespace BIT {
    int t[N];

    inline int lowbit(int x) {
        return x & -x;
    }

    inline void Add(int x, int k) {
        for( ; x <= n ; x += lowbit(x))
            t[x] += k;

        return ;
    }

    inline int Query(int x) {
        int res = 0;

        for( ; x ; x -= lowbit(x))
            res += t[x];

        return res;
    }
}

using namespace BIT;

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> B >> Q;
    for(int i = 1 ; i <= n ; ++ i)
        cin >> a[i], pre[i] = pre[i - 1] + a[i];

    for(int i = 1 ; i <= n ; ++ i)
        Add(i, a[i]), modify(i, pre[i] - i * B);

    while(Q --) {
        cin >> c >> x;

        add(c, n, x - a[c]);
        Add(c, x - a[c]);

        a[c] = x;

        int pos = binary();

        cout << fixed << setprecision(20) << (Query(pos) * 1.0 / pos * 1.0) << '\n';
    }

    return 0;
}