P1471 方差 · znzryb
## 思路讲解
## AC代码
[https://www.luogu.com.cn/record/230330272](https://www.luogu.com.cn/record/230330272)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#include <cfloat>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
// 参考了（抄了）beta99999 的提交 https://www.luogu.com.cn/record/216441078
// 因为自己重写的，目前只支持zkw线段树，配置上只保留了identity
// 采用0-based，左开右闭区间，注意这个区间转化
template <typename T,typename value_type> struct base_segtree{
int n,sz;
vector<value_type> tr,trsq;
static int bit_ceil(int x){int res=1;while(res<x){res<<=1;} return res;};
// zkw线段树开两倍大小，identity为默认值
base_segtree(int n):n(n),sz(bit_ceil(n)),tr((sz<<1),T::identity),trsq(sz<<1,T::identity){}
T *derived() { return static_cast<T*>(this); }
void pushup(int o){
tr[o]=T::op(tr[o<<1],tr[o<<1|1]);
trsq[o]=T::op(trsq[o<<1],trsq[o<<1|1]);
}
// zkw选配
int dis(int o){return __lg(sz)-__lg(o);} // 倒数第几层？有倒数第0层
int len(int o){return 1<<dis(o);} // （直接调用就可以，就是左闭右开区间长度）
int le(int o){return (o<<dis(o))-sz; } // 左闭
int rr(int o){return (o+1<<dis(o))-sz;} // 右开
// 单节点的下推 在子类中实现
// void pushdown(int o){}
void call_pushdown(int i){ // 把路径上的所有点向下推
int o=i+sz; // 1的__lg(1)=0，相当于就是从根节点慢慢推下来
for(int k=__lg(o);k>=__builtin_ctz(o) + 1;--k){
derived()->pushdown(o>>k);
}
}
void call_pushup(int i){
int o=i+sz;
// 这个下界你可能会很奇怪，为什么不是1？那么答案不在这里，而是在update函数
for(int k=__builtin_ctz(o) + 1;k<=__lg(o);++k){
derived()->pushup(o>>k);
}
}
void build(){
for(int o=sz-1;o>=1;--o){
derived()->pushup(o);
}
}
template<typename D>
void update(int l,int r,D x){
call_pushdown(l),call_pushdown(r);
int l0=l,r0=r;l+=sz,r+=sz;
for(;l<r;l>>=1,r>>=1){
if(l&1) derived()->settag(l++,x);
if(r&1) derived()->settag(--r,x); // 毕竟是右开区间
}
call_pushup(l0);call_pushup(r0);
}
value_type query(int l, int r){
call_pushdown(l);call_pushdown(r);
l+=sz;r+=sz; // T:: 调用的是类的静态成员，无需实例化
value_type resl=T::identity,resr=T::identity;
for(;l<r;l>>=1,r>>=1){
if(l&1) resl=T::op(resl,tr[l++]);
if(r&1) resr=T::op(tr[--r],resr);
}
return T::op(resl,resr);
}
value_type querysq(int l, int r){
call_pushdown(l);call_pushdown(r);
l+=sz;r+=sz; // T:: 调用的是类的静态成员，无需实例化
value_type resl=T::identity,resr=T::identity;
for(;l<r;l>>=1,r>>=1){
if(l&1) resl=T::op(resl,trsq[l++]);
if(r&1) resr=T::op(trsq[--r],resr);
}
return T::op(resl,resr);
}
void assign(int i,value_type a){
tr[i+sz]=a;
trsq[i+sz]=a*a;
}
};
// 主要要重载pushdown，构造函数，静态函数op，settag
struct segtree:base_segtree<segtree, DB>{
static constexpr DB identity = 0;
static DB op(const DB &a,const DB &b){
return a+b;
}
vdb tag;
segtree(int n):base_segtree(n),tag(sz,identity){}
void settag(int o,DB x){
ll ln=len(o);
trsq[o]+=(2*tr[o]*x+ln*x*x);
tr[o]+=x*ln;
if(o<sz) tag[o]+=x;
}
void pushdown(int o){
if(o>=sz) return;
if(abs(tag[o])<eps) return;
settag(o<<1,tag[o]);
settag(o<<1|1, tag[o]);
tag[o]=0;
}
};
constexpr DB segtree::identity;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--)
__();
return 0;
}
/*
*/
inline void __(){
cin>>N>>Q;
segtree tr(N);
FOR(i,0,N-1){
DB a;
cin>>a;
tr.assign(i, a);
}
tr.build();
FOR(i,1,Q){
ll op,l,r;
cin>>op>>l>>r;
DB len=r-l+1;
if(op==1){
DB x;cin>>x;
tr.update(l-1, r, x);
}else if(op==2){
DB res=tr.query(l-1, r)/len;
cout<<fsp(4)<<res<<"\n";
}else{
DB sum=tr.query(l-1, r),sumsq=tr.querysq(l-1, r);
DB aver=sum/len;
DB res=sumsq/len-aver*aver;
// DB res=sumsq-2*sum*aver+aver*aver*len;
// res/=len;
cout<<fsp(4)<<res<<"\n";
}
}
}
/*
AC
https://www.luogu.com.cn/record/230330272
8 15
8.46 6.03 3.73 0.32 7.43 3.71 8.04 8.22
3 1 8
1 2 8 -2.7566713364794850E+0000
1 2 8 2.1308819339610636E+0000
1 1 6 1.5912831262685359E+0000
1 1 8 -2.7779214559122920E+0000
1 1 8 -6.5134523715823889E-0001
3 2 8
1 1 6 -8.5440817382186651E-0001
3 2 8
2 2 8
3 2 7
1 3 8 -1.8737916438840330E+0000
1 1 7 2.5193137815222144E+0000
1 3 8 1.2835426828823984E+0000
3 3 8
ans:
7.4145
5.2609
6.2101
1.8256
6.1810
5.8854
暴力程序打出来的每一次操作后区域内的sqsum的值
sqsum:323.127
allsqsum:323.127
71.5716 36.3609 13.9129 0.1024 55.2049 13.7641 64.6416 67.5684
sqsum:98.1098
allsqsum:169.681
71.5716 10.7147 0.947369 5.93737 21.84 0.908836 27.9136 29.848
sqsum:207.387
allsqsum:278.959
71.5716 29.2055 9.63612 0.0935072 46.2973 9.51236 54.9705 57.672
sqsum:266.01
allsqsum:378.652
101.028 48.9369 22.0477 1.65249 70.4843 21.8602 54.9705 57.672
sqsum:156.444
allsqsum:156.444
52.9018 17.7879 3.67708 2.22734 31.5571 3.60078 21.4952 23.1966
sqsum:122.211
allsqsum:122.211
43.8511 12.718 1.60333 4.59576 24.6634 1.55308 15.8798 17.3468
sqsum:78.3601
allsqsum:122.211
43.8511 12.718 1.60333 4.59576 24.6634 1.55308 15.8798 17.3468
sqsum:66.8385
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468
sqsum:66.7998
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468
sqsum:66.7998
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468
sqsum:49.453
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468
sqsum:42.7848
allsqsum:83.4041
33.2653 7.35396 2.13736 23.7361 5.00877 2.19624 4.45696 5.24938
sqsum:147.84
allsqsum:153.09
68.6731 27.3647 1.11797 5.535 22.6323 1.07608 21.4412 5.24938
sqsum:96.2555
allsqsum:192.293
68.6731 27.3647 5.47974 1.14301 36.4923 5.3865 34.9755 12.7784
sqsum:96.2555
allsqsum:192.293
68.6731 27.3647 5.47974 1.14301 36.4923 5.3865 34.9755 12.7784
*/
```
:::
[https://www.luogu.com.cn/record/230330447](https://www.luogu.com.cn/record/230330447)
最优解。
## 心路历程（WA，TLE，MLE……）
### 线段树内部之间不要相互调用
P1471 方差
千万不要这么干，因为不仅更新的时候要调用，下传标记也要调用，你能保证两个线段树的懒标记状态一样吗？这个是不可能的，因为你也不可能同时更新，询问两个线段树，**除非把他们合为一个**。
::: 错误代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#include <cfloat>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
// 参考了（抄了）beta99999 的提交 https://www.luogu.com.cn/record/216441078
// 因为自己重写的，目前只支持zkw线段树，配置上只保留了identity
// 采用0-based，左开右闭区间，注意这个区间转化
template <typename T,typename value_type> struct base_segtree{
int n,sz;
vector<value_type> tr;
static int bit_ceil(int x){int res=1;while(res<x){res<<=1;} return res;};
// zkw线段树开两倍大小，identity为默认值
base_segtree(int n):n(n),sz(bit_ceil(n)),tr((sz<<1),T::identity){}
T *derived() { return static_cast<T*>(this); }
value_type val(int o){
// if(o<sz) return tr[o];
// int i=o-sz;
// if(i>=n) return T::identity;
return tr[o];
}
void pushup(int o){
tr[o]=T::op(val(o<<1),val(o<<1|1));
}
// zkw选配
int dis(int o){return __lg(sz)-__lg(o);} // 倒数第几层？有倒数第0层
int len(int o){return 1<<dis(o);} // （直接调用就可以，就是左闭右开区间长度）
int le(int o){return (o<<dis(o))-sz; } // 左闭
int rr(int o){return (o+1<<dis(o))-sz;} // 右开
// 单节点的下推 在子类中实现
// void pushdown(int o){}
void call_pushdown(int i){ // 把路径上的所有点向下推
int o=i+sz; // 1的__lg(1)=0，相当于就是从根节点慢慢推下来
for(int k=__lg(o);k>=__builtin_ctz(o) + 1;--k){
derived()->pushdown(o>>k);
}
}
void call_pushup(int i){
int o=i+sz;
// 这个下界你可能会很奇怪，为什么不是1？那么答案不在这里，而是在update函数
for(int k=__builtin_ctz(o) + 1;k<=__lg(o);++k){
derived()->pushup(o>>k);
}
}
void build(){
for(int o=sz-1;o>=1;--o){
derived()->pushup(o);
}
}
template<typename D>
void update(int l,int r,D x){
call_pushdown(l),call_pushdown(r);
int l0=l,r0=r;l+=sz,r+=sz;
for(;l<r;l>>=1,r>>=1){
if(l&1) derived()->settag(l++,x);
if(r&1) derived()->settag(--r,x); // 毕竟是右开区间
}
call_pushup(l0);call_pushup(r0);
}
value_type query(int l, int r){
call_pushdown(l);call_pushdown(r);
l+=sz;r+=sz; // T:: 调用的是类的静态成员，无需实例化
value_type resl=T::identity,resr=T::identity;
for(;l<r;l>>=1,r>>=1){
#ifdef LOCAL
debug(l);debug(r);
#endif
if(l&1) resl=T::op(resl,val(l++));
if(r&1) resr=T::op(val(--r),resr);
}
return T::op(resl,resr);
}
value_type& operator[](int i) {
return tr[i + sz];
}
// value_type get(int o){
// // for(int i=__lg(o);i>=__builtin_ctz(o)+1;--i){
// // derived()->pushdown(o>>i);
// // }
// call_pushdown(le(o));call_pushdown(rr(o));
// return tr[o];
// }
};
// 主要要重载pushdown，构造函数，静态函数op，settag
struct segtree:base_segtree<segtree, DB>{
static constexpr DB identity = 0;
static DB op(const DB &a,const DB &b){
return a+b;
}
vdb tag;
segtree(int n):base_segtree(n),tag(sz,identity){}
void settag(int o,DB x){
ll ln=len(o);
tr[o]+=x*ln;
if(o<sz) tag[o]+=x;
}
void pushdown(int o){
if(o>=sz) return;
if(abs(tag[o])<eps) return;
settag(o<<1,tag[o]);
settag(o<<1|1, tag[o]);
tag[o]=0;
}
};
struct sqsegtree:base_segtree<sqsegtree, DB>{
static constexpr DB identity = 0;
static DB op(const DB &a,const DB &b){
return a+b;
}
segtree& yici; // 指向外部的segtree实例
vdb tag;
sqsegtree(int n,segtree & yici):base_segtree(n),yici(yici),tag(sz,identity){}
void settag(int o,DB x){
DB cursum=yici.query(le(o),rr(o));
ll ln=len(o);
// #ifdef LOCAL
// debug(cursum);debug(tr[o]);
// #endif
tr[o]+=(2*cursum*x+ln*x*x);
if(o<sz) tag[o]+=x;
}
void pushdown(int o){
if(o>=sz) return;
if(abs(tag[o])<eps) return;
settag(o<<1,tag[o]);
settag(o<<1|1, tag[o]);
tag[o]=0;
}
};
constexpr DB segtree::identity;
constexpr DB sqsegtree::identity;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--)
__();
return 0;
}
/*
*/
inline void __(){
cin>>N>>Q;
segtree yici(N);
sqsegtree square(N,yici);
FOR(i,0,N-1){
DB a;
cin>>a;
// square.update(i, i+1, a);
// yici.update(i, i+1, a);
square[i]=a*a;
yici[i]=a;
}
square.build();yici.build();
FOR(i,1,Q){
ll op,l,r;
cin>>op>>l>>r;
DB len=r-l+1;
if(op==1){
DB x;cin>>x;
square.update(l-1, r, x);
yici.update(l-1, r, x);
}else if(op==2){
DB res=yici.query(l-1, r)/len;
cout<<fsp(4)<<res<<"\n";
}else{
DB sum=yici.query(l-1, r),sumsq=square.query(l-1, r);
DB aver=sum/len;
DB res=sumsq/len-aver*aver;
// DB res=sumsq-2*sum*aver+aver*aver*len;
// res/=len;
cout<<fsp(4)<<res<<"\n";
}
#ifdef LOCAL
FOR(j,1,N){
cerr<<square.query(j-1,j)<<" ";
}
cerr<<"\n";
#endif
}
}
/*
8 15
8.46 6.03 3.73 0.32 7.43 3.71 8.04 8.22
3 1 8
1 2 8 -2.7566713364794850E+0000
1 2 8 2.1308819339610636E+0000
1 1 6 1.5912831262685359E+0000
1 1 8 -2.7779214559122920E+0000
1 1 8 -6.5134523715823889E-0001
3 2 8
1 1 6 -8.5440817382186651E-0001
3 2 8
2 2 8
3 2 7
1 3 8 -1.8737916438840330E+0000
1 1 7 2.5193137815222144E+0000
1 3 8 1.2835426828823984E+0000
3 3 8
ans:
7.4145
5.2609
6.2101
1.8256
6.1810
5.8854
暴力程序打出来的每一次操作后区域内的sqsum的值
sqsum:323.127
allsqsum:323.127
71.5716 36.3609 13.9129 0.1024 55.2049 13.7641 64.6416 67.5684
sqsum:98.1098
allsqsum:169.681
71.5716 10.7147 0.947369 5.93737 21.84 0.908836 27.9136 29.848
sqsum:207.387
allsqsum:278.959
71.5716 29.2055 9.63612 0.0935072 46.2973 9.51236 54.9705 57.672
sqsum:266.01
allsqsum:378.652
101.028 48.9369 22.0477 1.65249 70.4843 21.8602 54.9705 57.672
sqsum:156.444
allsqsum:156.444
52.9018 17.7879 3.67708 2.22734 31.5571 3.60078 21.4952 23.1966
sqsum:122.211
allsqsum:122.211
43.8511 12.718 1.60333 4.59576 24.6634 1.55308 15.8798 17.3468
sqsum:78.3601
allsqsum:122.211
43.8511 12.718 1.60333 4.59576 24.6634 1.55308 15.8798 17.3468
sqsum:66.8385
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468
sqsum:66.7998
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468
sqsum:66.7998
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468
sqsum:49.453
allsqsum:100.065
33.2653 7.35396 0.169595 8.98909 16.9071 0.153522 15.8798 17.3468
sqsum:42.7848
allsqsum:83.4041
33.2653 7.35396 2.13736 23.7361 5.00877 2.19624 4.45696 5.24938
sqsum:147.84
allsqsum:153.09
68.6731 27.3647 1.11797 5.535 22.6323 1.07608 21.4412 5.24938
sqsum:96.2555
allsqsum:192.293
68.6731 27.3647 5.47974 1.14301 36.4923 5.3865 34.9755 12.7784
sqsum:96.2555
allsqsum:192.293
68.6731 27.3647 5.47974 1.14301 36.4923 5.3865 34.9755 12.7784
*/
```
:::