太闲了，找点毒瘤数据结构写。
题目传送门
这不一眼线段树吗？
对于我们的操作 \(2\)，我们知道平均数
\[d=\frac1n \sum_{i=1}^{n}a_i
\]
由于给定了区间长度 \(n\)，所以这个相当于查询区间和，数据结构基本操作。
对于我们的操作 \(3\)，我们知道方差
\[s^2=\frac1n \sum_{i=1}^{n}(a_i-d)^2
\]
展开
\[s^2=\frac1n \sum_{i=1}^{n} (a_i^2-2a_id+d^2)
\]
再展开
\[s^2=\frac1n (\sum_{i=1}^{n}a_i^2-2d\sum_{i=1}^{n}a_i+n\cdot d^2)
\]
注意到 \(\dfrac12\) 和 \(nd^2\) 还有 \(2d\) 均为定值，我们只需要在操作二的基础上维护一个平方和就行了。
其实可以只开一个线段树，但是我开了两个，这个实现还是很考细节的，害的我调了一下午。
code
#include <iostream>
#include <cmath>
#include <iomanip>
#define DEBUG
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;constexpr int mod = 998244353;
constexpr int maxn = 100005;ll n, q, opt, x, y;
lb k;lb a[maxn], tree[maxn << 2], ptree[maxn << 2], tag[maxn << 2], lazy[maxn << 2];//开两个线段树进行维护ll ls(ll p){return p << 1;
}ll rs(ll p){return p << 1 | 1;
}void pushup1(ll p){tree[p] = tree[ls(p)] + tree[rs(p)];
}void pushup2(ll p){ptree[p] = ptree[ls(p)] + ptree[rs(p)];
}void build1(ll p, ll pl, ll pr){if (pl == pr){tree[p] = a[pl];return;}ll mid = (pl + pr) >> 1;build1(ls(p), pl, mid);build1(rs(p), mid + 1, pr);pushup1(p);
}void build2(ll p, ll pl, ll pr){if (pl == pr){ptree[p] = a[pl] * a[pl];return;}ll mid = (pl + pr) >> 1;build2(ls(p), pl, mid);build2(rs(p), mid + 1, pr);pushup2(p);
}void addtag1(ll p, ll pl, ll pr, lb d){tag[p] += d;tree[p] += (pr - pl + 1) * d;
}void addtag2(ll p, ll pl, ll pr, lb d){lb sum = tree[p];lazy[p] += d;ptree[p] += 2 * d * sum + (pr - pl + 1) * d * d;//根据刚刚的推导
}void pushdown1(ll p, ll pl, ll pr){if (!tag[p])return;ll mid = (pl + pr) >> 1;addtag1(ls(p), pl, mid, tag[p]);addtag1(rs(p), mid + 1, pr, tag[p]);tag[p] = 0;
}void pushdown2(ll p, ll pl, ll pr){if (!lazy[p])return;ll mid = (pl + pr) >> 1;addtag2(ls(p), pl, mid, lazy[p]);addtag2(rs(p), mid + 1, pr, lazy[p]);lazy[p] = 0;
}
lb query1(ll L, ll R, ll p, ll pl, ll pr){if (L <= pl && pr <= R)return tree[p];pushdown2(p, pl, pr);pushdown1(p, pl, pr);//顺序很重要，不然你会像我一样调一下午，因为平方和的修改要用到原来的区间和ll mid = (pl + pr) >> 1;lb res = 0;if (L <= mid)res += query1(L, R, ls(p), pl, mid);if (mid < R)res += query1(L, R, rs(p), mid + 1, pr);return res;
}lb query2(ll L, ll R, ll p, ll pl, ll pr){if (L <= pl && pr <= R)return ptree[p];pushdown2(p, pl, pr);pushdown1(p, pl, pr);//同理ll mid = (pl + pr) >> 1;lb res = 0;if (L <= mid)res += query2(L, R, ls(p), pl, mid);if (mid < R)res += query2(L, R, rs(p), mid + 1, pr);return res;
}void update(ll L, ll R, ll p, ll pl, ll pr, lb d){if (L <= pl && pr <= R){addtag2(p, pl, pr, d);addtag1(p, pl, pr, d);//顺序return;}pushdown2(p, pl, pr);pushdown1(p, pl, pr);ll mid = (pl + pr) >> 1;if (L <= mid)update(L, R, ls(p), pl, mid, d);if (mid < R)update(L, R, rs(p), mid + 1, pr, d);pushup1(p);pushup2(p);
}int main() {fast;cin >> n >> q;for (ll i = 1; i <= n; i++)cin >> a[i];build1(1, 1, n);build2(1, 1, n);while (q--){cin >> opt;if (opt == 1){cin >> x >> y >> k;update(x, y, 1, 1, n, k);}else if (opt == 2){cin >> x >> y;cout << fixed << setprecision(4) << query1(x, y, 1, 1, n) / (y - x + 1) << endl;//按照要求保留四位小数输出}else {cin >> x >> y;lb pingjun = query1(x, y, 1, 1, n) / (y - x + 1);lb sqf = (query2(x, y, 1, 1, n) - 2 * pingjun * query1(x, y, 1, 1, n) + (y - x + 1) * pingjun * pingjun) / (y - x + 1);cout << fixed << setprecision(4) << sqf << endl;//根据方差计算公式}}return 0;
}