SDOI2017相关分析 线段树

题目

https://loj.ac/problem/2005

思路

\[ \sum_{L}^{R}{(x_i-x)^{2}} \]

\[ \sum_{L}^{R}{(x_i^2-2*x_i*x+x^{2})} \]

\[ \sum_{L}^{R}{x_i^2}-2*x*\sum_{L}^{R}x_i+(r-l+1)x^{2} \]

\[ \sum_{L}^{R}x_{i}^2-2*\frac{1}{r-l+1}(\sum_{L}^{R}x_i)^2+\frac{1}{r-l+1}*(\sum_{L}^{R}x)^2 \]

\[ \sum_{L}^{R}x_{i}*x_{i}-\frac{1}{r-l+1}\sum_{L}^{R}x_i*\sum_{L}^{R}x_i \]

\[ \sum_{L}^{R}(x_i-x)(y_i-y) \]

\[ \sum_{L}^{R}(x_i*y_i-x*y_i-y*x_i+x*y) \]

\[ \sum_{L}^{R}x_i*y_i-\sum_{L}^{R}x_i*y-\sum_{L}^{R}y_i*x+(r-l+1)*x*y \]

\[ \sum_{L}^{R}x_i*y_i-\frac{1}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}*y_i-\frac{1}{r-l+1}\sum_{L}^{R}*x_i\sum_{L}^{R}y_i+(r-l+1)*x*y \]

\[ \sum_{L}^{R}x_i*y_i-\frac{2}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}*y_i+\frac{1}{(r-l+1)}\sum_{L}^{R}x_i*\sum_{L}^{R}y_i \]

\[ \sum_{L}^{R}x_i*y_i-\frac{1}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}*y_i \]

\[ \frac{\sum_{L}^{R}x_i*y_i-\frac{1}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}*y_i}{\sum_{L}^{R}x_{i}*x_{i}-\frac{1}{r-l+1}\sum_{L}^{R}x_i\sum_{L}^{R}x_i} \]

其实不用这么麻烦的、、
好了，剩下的去维护吧
好吧，我太菜了
要开long doule

代码

#include <bits/stdc++.h>
#define ll long double
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=2e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for (;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for (;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
ll x[N],y[N];
struct node {
    int l,r,siz;
    ll tot[2],pingfang,chengji;
    ll lazy,S,T;
}e[N<<2];
void pushup(int rt) {
    e[rt].tot[0]=e[ls].tot[0]+e[rs].tot[0];
    e[rt].tot[1]=e[ls].tot[1]+e[rs].tot[1];
    e[rt].pingfang=e[ls].pingfang+e[rs].pingfang;
    e[rt].chengji=e[ls].chengji+e[rs].chengji;
}
ll calc(int x) {return (ll)x*(x+1)/2;};
ll calc2(int x) {return (ll)x*(x+1)/2*(2*x+1)/3;};
void pushdown(int rt) {
    if(e[rt].lazy) {
        e[ls].tot[0]=e[ls].tot[1]=calc(e[ls].r)-calc(e[ls].l-1);
        e[ls].pingfang=e[ls].chengji=calc2(e[ls].r)-calc2(e[ls].l-1);
        e[ls].S=e[ls].T=0;
        e[ls].lazy=1;

        e[rs].tot[0]=e[rs].tot[1]=calc(e[rs].r)-calc(e[rs].l-1);
        e[rs].pingfang=e[rs].chengji=calc2(e[rs].r)-calc2(e[rs].l-1);
        e[rs].S=e[rs].T=0;
        e[rs].lazy=1;

        e[rt].lazy=0;
    }
    if(e[rt].S||e[rt].T) {
        e[ls].chengji+=e[ls].tot[0]*e[rt].T+e[ls].tot[1]*e[rt].S+e[rt].S*e[rt].T*e[ls].siz;
        e[ls].pingfang+=e[ls].tot[0]*2*e[rt].S+e[rt].S*e[rt].S*e[ls].siz;
        e[ls].tot[0]+=e[ls].siz*e[rt].S;
        e[ls].tot[1]+=e[ls].siz*e[rt].T;
        e[ls].S+=e[rt].S;
        e[ls].T+=e[rt].T;
        
        e[rs].chengji+=e[rs].tot[0]*e[rt].T+e[rs].tot[1]*e[rt].S+e[rt].S*e[rt].T*e[rs].siz;
        e[rs].pingfang+=e[rs].tot[0]*2*e[rt].S+e[rt].S*e[rt].S*e[rs].siz;
        e[rs].tot[0]+=e[rs].siz*e[rt].S;
        e[rs].tot[1]+=e[rs].siz*e[rt].T;
        e[rs].S+=e[rt].S;
        e[rs].T+=e[rt].T;

        e[rt].S=e[rt].T=0;
    }
}
void build(int l,int r,int rt) {
    e[rt].l=l,e[rt].r=r,e[rt].siz=r-l+1;
    if(l==r) {
        e[rt].tot[0]=x[l];
        e[rt].tot[1]=y[l];
        e[rt].pingfang=x[l]*x[l];
        e[rt].chengji=x[l]*y[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushup(rt);
}
void modify_1(int L,int R,ll S,ll T,int rt) {
    if(L<=e[rt].l&&e[rt].r<=R) {
        e[rt].chengji+=e[rt].tot[0]*T+e[rt].tot[1]*S+S*T*e[rt].siz;
        e[rt].pingfang+=e[rt].tot[0]*2*S+S*S*e[rt].siz;
        e[rt].tot[0]+=e[rt].siz*S;
        e[rt].tot[1]+=e[rt].siz*T;
        e[rt].S+=S;
        e[rt].T+=T;
        return;
    }
    pushdown(rt);
    int mid=(e[rt].l+e[rt].r)>>1;
    if(L<=mid) modify_1(L,R,S,T,ls);
    if(R>mid) modify_1(L,R,S,T,rs);
    pushup(rt);
}
void modify_2(int L,int R,int rt) {
    if(L<=e[rt].l&&e[rt].r<=R) {
        e[rt].tot[0]=e[rt].tot[1]=calc(e[rt].r)-calc(e[rt].l-1);
        e[rt].pingfang=e[rt].chengji=calc2(e[rt].r)-calc2(e[rt].l-1);
        e[rt].S=e[rt].T=0;
        e[rt].lazy=1;
        return;
    }
    pushdown(rt);
    int mid=(e[rt].l+e[rt].r)>>1;
    if(L<=mid) modify_2(L,R,ls);
    if(R>mid) modify_2(L,R,rs);
    pushup(rt);
}
ll query(int L,int R,int opt,int rt) {
    if(L<=e[rt].l&&e[rt].r<=R) {
        if(opt==0) return e[rt].tot[0];
        if(opt==1) return e[rt].tot[1];
        if(opt==2) return e[rt].pingfang;
        if(opt==3) return e[rt].chengji;
    }
    pushdown(rt);
    int mid=(e[rt].l+e[rt].r)>>1;
    ll ans=0;
    if(L<=mid) ans+=query(L,R,opt,ls);
    if(R>mid) ans+=query(L,R,opt,rs);
    pushup(rt);
    return ans;
}
int main() {
    int n=read(),m=read();
    for(int i=1;i<=n;++i) x[i]=read();
    for(int i=1;i<=n;++i) y[i]=read();
    build(1,n,1);
    while(m--) {
        int opt=read(),L=read(),R=read();
        if(opt==1) {
            ll tot_x=query(L,R,0,1);
            ll tot_y=query(L,R,1,1);
            ll tot_x_x=query(L,R,2,1);
            ll tot_x_y=query(L,R,3,1);
            long double a=tot_x_y-tot_x*tot_y/(R-L+1);
            long double b=tot_x_x-tot_x*tot_x/(R-L+1);
            printf("%.10Lf\n",(long double)a/b);
        } else if(opt==2) {
            ll S=read(),T=read();
            modify_1(L,R,(ll)S,(ll)T,1);
        } else {
            ll S=read(),T=read();
            modify_2(L,R,1);
            modify_1(L,R,(ll)S,(ll)T,1);
        }
    }
    return 0;
}