鬼畜线段树……Orz Capella
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, uu, vv, opt;
double xx[100005], yy[100005], ss, tt, faq[4];
struct SGT{
double val[400005][4], stag[400005], ttag[400005];
/*
* val[0]: x_i^2
* val[1]: x_i
* val[2]: y_i
* val[3]: x_i*y_i
*/
bool ismo[400005];
void pushUp(int o, int lson, int rson){
for(int i=0; i<4; i++)
val[o][i] = val[lson][i] + val[rson][i];
}
double calc(int x){
return (double)x*(x+1)*(2*x+1)/6.0;
}
void pushModify(int o, int l, int r){
val[o][0] = val[o][3] = calc(r) - calc(l-1);
val[o][1] = val[o][2] = (double)(l+r) * (r-l+1) / 2.0;
ismo[o] = true;
stag[o] = ttag[o] = 0.0;
}
void pushAdd(int o, int l, int r, double s, double t){
int siz=r-l+1;
val[o][0] += 2.0*s*val[o][1] + s*s*siz;
val[o][3] += s*val[o][2] + t*val[o][1] + s*t*siz;
val[o][1] += s * siz;
val[o][2] += t * siz;
stag[o] += s;
ttag[o] += t;
}
void pushDown(int o, int l, int r, int lson, int rson, int mid){
if(ismo[o]){
if(l<=mid) pushModify(lson, l, mid);
if(mid<r) pushModify(rson, mid+1, r);
}
if(l<=mid) pushAdd(lson, l, mid, stag[o], ttag[o]);
if(mid<r) pushAdd(rson, mid+1, r, stag[o], ttag[o]);
stag[o] = ttag[o] = ismo[o] = 0;
}
void build(int o, int l, int r){
if(l==r){
val[o][0] = xx[l] * xx[l];
val[o][1] = xx[l]; val[o][2] = yy[l];
val[o][3] = xx[l] * yy[l];
}
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(l<=mid) build(lson, l, mid);
if(mid<r) build(rson, mid+1, r);
pushUp(o, lson, rson);
}
}
void update(int o, int l, int r, int x, int y, double s, double t){
// printf("faQ
");
if(l>=x && r<=y) pushAdd(o, l, r, s, t);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
pushDown(o, l, r, lson, rson, mid);
if(x<=mid) update(lson, l, mid, x, y, s, t);
if(mid<y) update(rson, mid+1, r, x, y, s, t);
pushUp(o, lson, rson);
}
}
void modify(int o, int l, int r, int x, int y, double s, double t){
if(l>=x && r<=y){
pushModify(o, l, r);
pushAdd(o, l, r, s, t);
}
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
pushDown(o, l, r, lson, rson, mid);
if(x<=mid) modify(lson, l, mid, x, y, s, t);
if(mid<y) modify(rson, mid+1, r, x, y, s, t);
pushUp(o, lson, rson);
}
}
void query(int o, int l, int r, int x, int y){
if(l>=x && r<=y){
for(int i=0; i<4; i++)
faq[i] += val[o][i];
}
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
pushDown(o, l, r, lson, rson, mid);
if(x<=mid) query(lson, l, mid, x, y);
if(mid<y) query(rson, mid+1, r, x, y);
}
}
}sgt;
double queryRange(int l, int r){
for(int i=0; i<4; i++) faq[i] = 0.0;
sgt.query(1, 1, n, l, r);
return (faq[3]-faq[1]*faq[2]/(r-l+1)) / (faq[0]-faq[1]*faq[1]/(r-l+1));
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++)
scanf("%lf", &xx[i]);
for(int i=1; i<=n; i++)
scanf("%lf", &yy[i]);
sgt.build(1, 1, n);
while(m--){
scanf("%d", &opt);
if(opt==1){
scanf("%d %d", &uu, &vv);
printf("%.10f
", queryRange(uu, vv));
}
else if(opt==2){
scanf("%d %d %lf %lf", &uu, &vv, &ss, &tt);
sgt.update(1, 1, n, uu, vv, ss, tt);
}
else{
scanf("%d %d %lf %lf", &uu, &vv, &ss, &tt);
sgt.modify(1, 1, n, uu, vv, ss, tt);
}
}
return 0;
}