Новый скринсейвер

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;

ld d(ld a, ld b) {
    if (!b)
        return 0;
    return a / b;
}

struct Fenwick {
    vector<ld> t;
    int n;
    void init (int nn)
    {
        n = nn;
        t.resize(n);
    }
    ld sum (int r)
    {
        ld ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            ret += t[r];
        }
        return ret;
    }
    void inc (int i, ld add)
    {
        for (; i < n; i = (i | (i + 1))) {
            t[i] += add;
        }
    }
    ld sum (int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
};

const int DOSZ = 1005;
const int MAXS = 1e+5;

Fenwick a[6], c[6];

void add(ld cur, ld ab, int pl) {
    a[0].inc(cur, pl * cur);
    a[1].inc(cur, pl * d(1.0, ab));
    a[2].inc(cur, pl * d(cur, ab));
    a[3].inc(cur, pl * d(cur * cur, 2 * ab));
    a[4].inc(cur, pl * 0.5 * ab);
    a[5].inc(cur, pl);
    c[0].inc(cur + ab, pl * cur);
    c[1].inc(cur + ab, pl * d(1.0, ab));
    c[2].inc(cur + ab, pl * d(cur, ab));
    c[3].inc(cur + ab, pl * d(cur * cur, 2 * ab));
    c[4].inc(cur + ab, pl * 0.5 * ab);
    c[5].inc(cur + ab, pl);
}

ld calc(Fenwick * a, ld hh) {
    return hh * a[5].sum(0, hh - 1) - (hh * hh * 1.0 / 2) * a[1].sum(0, hh - 1) + hh * a[2].sum(0, hh - 1) - a[3].sum(0, hh - 1) - a[0].sum(0, hh - 1);
}

int h[MAXS];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 0; i < 6; ++i)
    {
        a[i].init(DOSZ);
        c[i].init(DOSZ);
    }

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    for (int i = 0; i + 1 < n; ++i) {
        int cur = min(h[i], h[i + 1]);
        int ab = max(h[i], h[i + 1]) - cur;
        add(cur, ab, 1);
    }

    for (int i = 0; i < m; ++i) {
        char q;
        cin >> q;
        if (q == 'Q') {
            int hh;
            cin >> hh;
            ld res = a[0].sum(0, hh);
            res += hh * a[5].sum(hh + 1, DOSZ - 1);
            res += calc(a, hh);
            res -= calc(c, hh);
            res += c[4].sum(0, hh - 1);
            printf("%.4Lf\n", (n - 1) * hh - res);
        }
        else {
            int id, newh;
            cin >> id >> newh;
            if (id + 1 < n) {
                int cur = min(h[id], h[id + 1]);
                int ab = max(h[id], h[id + 1]) - cur;
                add(cur, ab, -1);
                cur = min(h[id + 1], newh);
                ab = max(h[id + 1], newh) - cur;
                add(cur, ab, 1);
            }
            if (id - 1 > -1) {
                int cur = min(h[id], h[id - 1]);
                int ab = max(h[id], h[id - 1]) - cur;
                add(cur, ab, -1);
                cur = min(h[id - 1], newh);
                ab = max(h[id - 1], newh) - cur;
                add(cur, ab, 1);
            }
            h[id] = newh;
        }
    }


    return 0;
}