RT,公式推对了,线段树应该没问题,0ptsWA求条
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int n , m;
double t1[maxn<<2] , t2[maxn<<2] , tag[maxn<<2] , a[maxn];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void PushUp(int p){t1[p]=t1[ls(p)]+t1[rs(p)],t2[p]=t2[ls(p)]+t2[rs(p)];}
inline void PushDown(int p , int l , int r)
{
int mid = l + r >> 1;
t2[ls(p)]+=tag[p]*2.0*t1[ls(p)]+tag[p]*tag[p]*(mid - l + 1);
t2[rs(p)]+=tag[p]*2.0*t1[rs(p)]+tag[p]*tag[p]*(r - mid);
t1[ls(p)]+=tag[p]*(mid - l + 1);
t1[ls(p)]+=tag[p]*(r - mid);
tag[ls(p)]+=tag[p];
tag[rs(p)]+=tag[p];
tag[p]=0;
return;
}
void Build(int p , int l , int r)
{
if (l == r){t1[p]=a[l],t2[p]=a[l]*a[l];return;}
int mid = l + r >> 1;
Build(ls(p) , l , mid);
Build(rs(p) , mid + 1 , r);
PushUp(p);
return;
}
void Update(int p , int l , int r , int L , int R , double val)
{
if (L <= l && r <= R)
{
t2[p]+=val*2.0*t1[p]+val*val*(r - l + 1);
t1[p]+=val*(r - l + 1);
tag[p]+=val;
return;
}
PushDown(p , l , r);
int mid = l + r >> 1;
if (L <= mid)Update(ls(p) , l , mid , L , R , val);
if (R > mid)Update(rs(p) , mid + 1 , r , L , R , val);
PushUp(p);
return;
}
double QuerySum(int p , int l , int r , int L , int R)
{
if (L <= l && r <= R) return t1[p];
PushDown(p , l , r);
int mid = l + r >> 1;
double res = 0;
if (L <= mid)res+=QuerySum(ls(p) , l , mid , L , R);
if (R > mid)res+=QuerySum(rs(p) , mid + 1 , r , L , R);
return res;
}
double QueryPowSum(int p , int l , int r , int L , int R)
{
if (L <= l && r <= R) return t2[p];
PushDown(p , l , r);
int mid = l + r >> 1;
double res = 0;
if (L <= mid)res+=QueryPowSum(ls(p) , l , mid , L , R);
if (R > mid)res+=QueryPowSum(rs(p) , mid + 1 , r , L , R);
return res;
}
int main ()
{
// freopen("in.txt" , "r" , stdin);
scanf("%d%d" , &n , &m);
for (int i = 1; i <= n; i++)scanf("%lf" , &a[i]);
Build(1 , 1 , n);
while(m--)
{
int op , l , r;
double k = 0;
scanf("%d%d%d" , &op , &l , &r);
if (op == 1)scanf("%lf" , &k),Update(1 , 1 , n , l , r , k);
else if (op == 2)printf("%.4lf\n" , QuerySum(1 , 1 , n , l , r) / (r - l + 1));
else
{
double sum = QuerySum(1 , 1 , n , l , r)/(r - l + 1) , len = r - l + 1;
printf("%.4lf\n" , QueryPowSum(1 , 1 , n , l , r)/len - (sum * sum));
}
}
return 0;
}