样例过了,但是爆0。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 20;
ll n, m, opt;
double tag[N], k, a[N];
struct data {
double sum, nul;
}tree[4 * N];
inline ll ls(ll x) {return x << 1;}
inline ll rs(ll x) {return x << 1 | 1;}
data build(ll p, ll l, ll r) {
data tmp;
tmp.nul = tmp.sum = 0.0;
if(l == r) {
tmp.sum = tree[p].sum = a[l];
tmp.nul = tree[p].nul = a[l] * a[l];
return tmp;
}
ll mid = (l + r) / 2;
data tmpl = build(ls(p), l, mid), tmpr = build(rs(p), mid + 1, r);
tree[p].sum = tmpl.sum + tmpr.sum;
tree[p].nul = tmpl.nul + tmpr.nul;
return tree[p];
}
void up(ll p) {
tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;
tree[p].nul = tree[ls(p)].nul + tree[rs(p)].nul;
return;
}
void down(ll p, ll l, ll r) {
/*
tree[p].sum += (r - l + 1) * k;
tree[p].nul += n * k * k + 2 * k * query_sum(1, 1, n, l, r);
tag[p] += k;
*/
if(tag[p] == 0.0) return;
ll mid = (l + r) / 2;
tag[ls(p)] += tag[p];
tag[rs(p)] += tag[p];
tree[ls(p)].nul += (mid - l + 1) * tag[p] * tag[p] + 2.0 * tag[p] * tree[p].sum;
tree[rs(p)].nul += (r - mid) * tag[p] * tag[p] + 2.0 * tag[p] * tree[p].sum;
tree[ls(p)].sum += (mid - l + 1) * tag[p];
tree[rs(p)].sum += (r - mid) * tag[p];
// tag[ls(p)] += tag[p];
// tag[rs(p)] += tag[p];
tag[p] = 0.0;
return;
}
double query_sum(ll p, ll l, ll r, ll L, ll R) {
double res = 0;
if(L <= l && r <= R) {
return tree[p].sum;
}
down(p, l, r);
ll mid = (l + r) / 2;
if(L <= mid) res += query_sum(ls(p), l, mid, L, R);
if(R > mid) res += query_sum(rs(p), mid + 1, r, L, R);
up(p);
return res;
}
double query_nul(ll p, ll l, ll r, ll L, ll R) {
double res = 0;
if(L <= l && r <= R) {
return tree[p].nul;
}
down(p, l, r);
ll mid = (l + r) / 2;
if(L <= mid) res += query_nul(ls(p), l, mid, L, R);
if(R > mid) res += query_nul(rs(p), mid + 1, r, L, R);
up(p);
return res;
}
void add(ll p, ll l, ll r, ll L, ll R, double k) {
if(L <= l && r <= R) {
tree[p].nul += (r - l + 1) * k * k + 2 * k * tree[p].sum;
tree[p].sum += (r - l + 1) * k;
tag[p] += k;
return;
}
down(p, l, r);
ll mid = (l + r) / 2;
if(L <= mid) add(ls(p), l, mid, L, R, k);
if(R > mid) add(rs(p), mid + 1, r, L, R, k);
up(p);
return;
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
for(int i = 1; i <= m; i++) {
double x, y;
cin >> opt >> x >> y;
if(opt == 1) {
cin >> k;
add(1, 1, n, x, y, k);
}
if(opt == 2) {
if(x > y) swap(x, y);
printf("%.4lf\n",query_sum(1, 1, n, x, y) / (y - x + 1));
}
if(opt == 3) {
if(x > y) swap(x, y);
double S = query_sum(1, 1, n, x, y) / (y - x + 1), NUL = query_nul(1, 1, n, x, y) / (y - x + 1);
double ANS = NUL - (S * S);
printf("%.4lf\n",ANS);
}
}
return 0;
}
//2 250 P