ABC292Ex减去平均值线段树维护前缀和区间加

1、Rating计算规则为每场比赛得分的平均值。
2、每场比赛成绩为得分减去定值b
3、Rating达到m后，不再改变。
现在会动态修改某一场比赛成绩，请问最终Rating是多少？

如果没有达到m，那么只需要求总和即可；
达到m则需要知道那一场比赛后，不算Rating。
为了方便查找，我们可以让每场比赛成绩先减去b，这样维护前缀和，第一个非负数位置即计算Rating的最后一场比赛。
对于单点修改，后面的前缀和都需要增加差值，区间加可以用线段树维护。

#include <bits/stdc++.h>
using namespace std;
const int N=1<<20|9;
int n, m, i, j, k, b, x, a[N];
long long s[N], f[N], d[N];
void xia(int p, int l, int r){
    int m=l+r>>1, lc=p<<1, rc=lc|1;
    s[lc] += (m-l+1)*f[p], f[lc] += f[p], d[lc] += f[p];
    s[rc] += (r-m)*f[p], f[rc] += f[p], d[rc] += f[p];
    f[p] = 0;
}
void add(int p, int l, int r, int x, int y, long long z){
    if(x<=l && r<=y) s[p] += (r-l+1)*z, f[p] += z, d[p] += z;
    else{
        int m=l+r>>1, lc=p<<1, rc=lc|1;
        if(f[p]) xia(p, l, r);
        if(x <= m) add(lc, l, m, x, y, z);
        if(y > m) add(rc, m+1, r, x, y, z);
        s[p] = s[lc] + s[rc];//没必要，用不到
        d[p] = max(d[lc], d[rc]);//维护区间最大值
    }
}
void cha(int p, int l, int r){
    if(l == r){
        printf("%.15lf\n", b+1.0*s[p]/r);
        return;//前r场比赛计算Rating
    }
    int m=l+r>>1, lc=p<<1, rc=lc|1;
    if(f[p]) xia(p, l, r);
    if(d[lc] >= 0) cha(lc, l, m);//左边有非负
    else cha(rc, m+1, r);//否则找右边
}//如果不存在非负，最终会全部算
int main(){
    scanf("%d%d%d", &n, &b, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        add(1, 1, n, i, n, a[i]-b);
    }//前缀和[i, n]均发生修改
    while(m--){
        scanf("%d%d", &i, &x);
        add(1, 1, n, i, n, x-a[i]);
        a[i] = x;
        cha(1, 1, n);//查找第一个非负前缀和位置
    }
    return 0;
}