p3707 分块

· · 题解

p3707

这道题第一次写了一颗线段树，（ 只有样例过了 ） 始终没有调出来，于是写了一个分块。

首先要化简本题的阴间式子

a=\frac{\sum^R_{i=L}(x_i-\bar{x})(y_i-\bar{y})}{\sum^R_{i=L}(x_i-\bar{x})^2}

以下为分子：

=\sum^R_{i=L} (x_iy_i-x_i\bar{y}-y_i\bar{x}+\bar{x}\bar{y}) =\sum^R_{i=L} x_iy_i-\bar{y}\sum^R_{i=L}x_i-\bar{x}\sum^R_{i=L}y_i+\sum^R_{i=L}\bar{x}\bar{y}

把 \bar x 和 \bar y 展开：

=\sum^R_{i=L} x_iy_i-\frac{\sum^R_{i=L} x_i\sum^R_{i=L} y_i}{R-L+1}-\frac{\sum^R_{i=L} x_i\sum^R_{i=L} y_i}{R-L+1}+\frac{\sum^R_{i=L} x_i\sum^R_{i=L} y_i}{R-L+1} =\sum^R_{i=L} x_iy_i-\frac{\sum^R_{i=L} x_i\sum^R_{i=L} y_i}{R-L+1}

分母同理：

=\sum^R_{i=L} x_i^2-\frac{(\sum^R_{i=L} x_i)^2}{R-L+1}

于是，原来的式子就被化成了下面的形式：

a=\frac{\sum^R_{i=L} x_iy_i-\frac{\sum^R_{i=L} x_i\sum^R_{i=L} y_i}{R-L+1}}{\sum^R_{i=L} x_i^2-\frac{(\sum^R_{i=L} x_i)^2}{R-L+1}}

所以我们只需要维护 \sum x_i \sum y_i \sum x_iy_i \sum x_i^2 ，对于区间加和区间覆盖操作，我们可以维护标记 add 和 cover 。

操作 2：

\sum (x_i+s)(y_i+t)=\sum x_iy_i+s\sum y_i+t\sum x_i+st(R-L+1) \sum (x_i+s)^2=\sum x_i^2+2s\sum x_i+s^2(R-L+1)

之后再更新 \sum x_i \sum y_i 并记录 add 。

操作 3：

每个块直接清空 add 标记，并记录 cover ,然后直接用平方和公式 （ \frac{n(n+1)(2n+1)}{6} ） 维护信息。

对于碎块，直接暴力计算更改产生的贡献。

注意

存在覆盖标记的碎块在进行更改时可能产生混淆，所以可以直接 清空整个块的所有标记 再进行更改 （ 先覆盖再修改 ）

可能可行的优化：

  1. 略微调低块的大小

  2. O2yyds

可能存在的更改

code

细节可以看代码 （ 码风自我感觉良好 ） 

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
const int maxn=100010;
double x[maxn],y[maxn];
int n,m,K;
struct block {
    int l,r;
    double x2,xy,x,y;
    double add[2];//区间加标记
    double cvr[2];//区间覆盖标记
    bool c;
} b[maxn];
int id[maxn];
void clear(int t) {//清空整个块
    if(b[t].c) {
        b[t].c=0;
        for(int i=b[t].l; i<=b[t].r; i++) {
            x[i]=b[t].cvr[0]+i;
            y[i]=b[t].cvr[1]+i;
        }
        b[t].cvr[0]=b[t].cvr[1]=0;
    }
    if(b[t].add[0]||b[t].add[1]) {
        int S=b[t].add[0];
        int T=b[t].add[1];
        for(int i=b[t].l; i<=b[t].r; i++) {
            x[i]+=S;
            y[i]+=T;
        }
        b[t].add[0]=b[t].add[1]=0;
    }
}
void add(int l,int r,double s,double t) {
    clear(id[l]);
    clear(id[r]);
    for(int i=l; i<=b[id[l]].r&&i<=r; i++) {
        b[id[l]].x2+=2*s*x[i]+s*s;
        b[id[l]].xy+=s*y[i]+t*x[i]+s*t;
        b[id[l]].x+=s;
        b[id[l]].y+=t;
        x[i]+=s;
        y[i]+=t;
    }
    if(id[l]!=id[r])
        for(int i=b[id[r]].l; i<=r; i++) {
            b[id[r]].x2+=2*s*x[i]+s*s;
            b[id[r]].xy+=s*y[i]+t*x[i]+s*t;
            b[id[r]].x+=s;
            b[id[r]].y+=t;
            x[i]+=s;
            y[i]+=t;
        }
    for(int i=id[l]+1; i<id[r]; i++) {
        b[i].x2+=2*b[i].x*s+s*s*(b[i].r-b[i].l+1);
        b[i].xy+=b[i].x*t+b[i].y*s+s*t*(b[i].r-b[i].l+1);
        b[i].x+=s*(b[i].r-b[i].l+1);
        b[i].y+=t*(b[i].r-b[i].l+1);
        b[i].add[0]+=s;
        b[i].add[1]+=t;
    }
    return;
}
void cover(int l,int r,double s,double t) {
    clear(id[l]);
    clear(id[r]);
    for(int i=l; i<=b[id[l]].r&&i<=r; i++) {
        b[id[l]].x2-=x[i]*x[i]-(s+i)*(s+i);
        b[id[l]].xy-=x[i]*y[i]-(s+i)*(t+i);
        b[id[l]].x-=x[i]-(s+i);
        b[id[l]].y-=y[i]-(t+i);
        x[i]=s+i;
        y[i]=t+i;
    }
    if(id[l]!=id[r])
        for(int i=b[id[r]].l; i<=r; i++) {
            b[id[r]].x2-=x[i]*x[i]-(s+i)*(s+i);
            b[id[r]].xy-=x[i]*y[i]-(s+i)*(t+i);
            b[id[r]].x-=x[i]-(s+i);
            b[id[r]].y-=y[i]-(t+i);
            x[i]=s+i;
            y[i]=t+i;//暴力计算贡献
        }
    for(int i=id[l]+1; i<id[r]; i++) {
        int l=b[i].l;
        int r=b[i].r;
            //平方和公式维护信息
        b[i].x2=(r-l+1)*s*s+s*(l+r)*(r-l+1)+r*(r+1)*(2*r+1)/6-l*(l-1)*(2*l-1)/6;
        b[i].xy=(r-l+1)*s*t+(s+t)*(l+r)*(r-l+1)/2+r*(r+1)*(2*r+1)/6-l*(l-1)*(2*l-1)/6;
        b[i].x=(r-l+1)*s+(l+r)*(r-l+1)/2;
        b[i].y=(r-l+1)*t+(l+r)*(r-l+1)/2;
        b[i].cvr[0]=s;
        b[i].cvr[1]=t;
        b[i].add[0]=b[i].add[1]=0;
        b[i].c=1;
    }
    return;
}
struct Ans {
    double x,y,xy,x2;
} ans;
double query(int l,int r) {
    ans.x=ans.x2=ans.xy=ans.y=0;
    clear(id[l]);
    clear(id[r]);
    for(int i=l; i<=b[id[l]].r; i++) {
        ans.x+=x[i];
        ans.y+=y[i];
        ans.x2+=x[i]*x[i];
        ans.xy+=x[i]*y[i];
    }
    if(id[l]!=id[r])
        for(int i=b[id[r]].l; i<=r; i++) {
            ans.x+=x[i];
            ans.y+=y[i];
            ans.x2+=x[i]*x[i];
            ans.xy+=x[i]*y[i];
        }
    for(int i=id[l]+1; i<id[r]; i++) {
        ans.x+=b[i].x;
        ans.y+=b[i].y;
        ans.x2+=b[i].x2;
        ans.xy+=b[i].xy;
    }
    return (ans.xy-ans.x*ans.y/(r - l + 1))/(ans.x2-ans.x*ans.x/(r - l + 1));
}

signed main() {
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%Lf",x+i);
    }
    for(int i=1; i<=n; i++) {
        scanf("%Lf",y+i);
    }
    K=sqrt(n);
    for(int i=1; i<=n; i++) {
        id[i]=(i-1)/K+1;
        b[id[i]].x+=x[i];
        b[id[i]].y+=y[i];
        b[id[i]].x2+=x[i]*x[i];
        b[id[i]].xy+=x[i]*y[i];
    }
    for(int i=1; i<=id[n]; i++) {
        b[i].l=(i-1)*K+1;
        b[i].r=i*K;
    }
    b[id[n]].r=n;
    for(int i=1; i<=m; i++) {
        int in,l,r;
        double s,t;
        scanf("%lld%lld%lld",&in,&l,&r);
        switch(in) {
            case 1:
                printf("%.10Lf\n",query(l,r));
                break;
            case 2:
                scanf("%Lf%Lf",&s,&t);
                add(l,r,s,t);
                break;
            case 3:
                scanf("%Lf%Lf",&s,&t);
                cover(l,r,s,t);
                break;
        }
    }
}