基本的な方針は公式解説と同じです。

公式解説では、\(q_i\) をうまく扱うことで、prefix sumの計算及びprefix sumのprefix maxを求める操作をセグ木で処理していますが、ここでは \(q_i\) のprefix sumを直接扱うことを考えます。このとき、クエリを処理するために必要な操作は次の2つです。

• 区間加算 (\(q_i\) の1点更新に対応)
• prefix max が初めて0以上になる箇所を高速に求める

これは区間add区間maxの遅延セグメントツリーにより処理することができます。

#include<bits/stdc++.h>
#include<atcoder/lazysegtree>
using namespace std;
#define rep(i,l,r)for(int i=(l);i<(r);i++)
using ll=long long;
const ll INF=(ll)1e18;

using S=ll;
using F=ll;
S op(S x,S y){return max(x,y);}
S mapping(F t,S x){return t+x;}
F composition(F t,F s){return t+s;}
S e(){return -INF;}
F id(){return 0;}

int main(){
  int n,b,q;
  cin >> n >> b >> q;
  vector<ll>a(n);
  rep(i,0,n)cin >> a[i];
  vector<ll>sum(n);
  sum[0]=a[0]-b;
  rep(i,1,n)sum[i]=sum[i-1]+a[i]-b;
  
  atcoder::lazy_segtree<S,op,e,F,mapping,composition,id>seg(sum);
  
  while(q--){
    int c,x;
    cin >> c >> x;
    c--;
    ll diff=x-a[c];
    a[c]=x;
    seg.apply(c,n,diff);
    int i=seg.max_right(0,[](S x){return x<0;});
    if(i==n)i=n-1;
    printf("%.10f\n",(double)seg.get(i)/(i+1)+b);
  }
}