显然这题需要线段树。

然后开始口胡,第二个操作可以打加法标记,第三个操作等于清空区间然后打上一个每个值需要加上下标 $i$ 的标记,然后做一个第二个操作即可。

接下来考虑第一个操作,看看题目要我们维护些什么。

$$ \begin{aligned} a&=\frac{\sum\limits_{i=L}^R(x_i-\bar{x})(y_i-\bar{y})}{\sum\limits_{i=L}^R(x_i-\bar{x})^2}\\ \end{aligned} $$

上下两个可以分开,先看上面的分子。

$$ \begin{aligned} res1&=\sum\limits_{i=L}^R(x_i-\bar{x})(y_i-\bar{y})\\ &=\sum\limits_{i=L}^Rx_iy_i-\bar{x}y_i-x_i\bar{y}+\bar{x}\bar{y}\\ &=\sum\limits_{i=L}^Rx_iy_i-\bar{x}\bar{y}(R-L+1)\\ \end{aligned} $$

然后看下面的分母:

$$ \begin{aligned} res2&=\sum\limits_{i=L}^R(x_i-\bar{x})^2\\ &=\sum\limits_{i=L}^Rx_i^2-2x_i\bar{x}+\bar{x}^2\\ &=\sum\limits_{i=L}^Rx_i^2-2\bar{x}\sum\limits_{i=L}^Rx_i+(R-L+1)\bar{x}^2\\ &=\sum\limits_{i=L}^Rx_i^2-\bar{x}^2(R-L+1)\\ \end{aligned} $$

显然 $\bar{x}$ 和 $\bar{y}$ 都很好求,然后我们的线段树只需要维护一下:

$$ \begin{cases} \sum_{i=L}^{R}x_i\\ \sum_{i=L}^{R}y_i\\ \sum_{i=L}^{R}x_i^2\\ \sum_{i=L}^{R}x_iy_i\\ \end{cases} $$

即可。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+2;
int n,m;ll X[N],Y[N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Node {double sx,sy,sx2,sxy,tx,ty;bool ti;}t[N<<2];
struct Segment_Tree {
    #define mid ((l+r)>>1)
    #define len (r-l+1)
    inline double calc1(int x) {return 1.0*x*(x+1)/2;}
    inline double calc2(int x) {return 1.0*x*(x+1)*(2*x+1)/6;}
    inline void modify_y(int x,int l,int r,ll v) {
        t[x].sxy+=1.0*v*t[x].sx,t[x].sy+=1.0*len*v,t[x].ty+=v;
    }
    inline void modify_x(int x,int l,int r,ll v) {
        t[x].sx2+=1.0*len*v*v+2.0*t[x].sx*v,t[x].sxy+=1.0*v*t[x].sy,t[x].sx+=1.0*len*v,t[x].tx+=v;
    }
    inline void clear(int x,int l,int r) {
        t[x].tx=t[x].ty=0,t[x].ti=1,
        t[x].sx=t[x].sy=calc1(r)-calc1(l-1),t[x].sx2=t[x].sxy=calc2(r)-calc2(l-1);
    }
    inline void pushdown(int x,int l,int r) {
        if(t[x].ti) clear(x<<1,l,mid),clear(x<<1|1,mid+1,r),t[x].ti=0;
        if(t[x].tx) modify_x(x<<1,l,mid,t[x].tx),modify_x(x<<1|1,mid+1,r,t[x].tx),t[x].tx=0;
        if(t[x].ty) modify_y(x<<1,l,mid,t[x].ty),modify_y(x<<1|1,mid+1,r,t[x].ty),t[x].ty=0;
    }
    inline Node merge(Node a,Node b) {
        return (Node){a.sx+b.sx,a.sy+b.sy,a.sx2+b.sx2,a.sxy+b.sxy,0,0,0};
    }
    void build(int x,int l,int r) {
        if(l==r) {t[x]=(Node){1.0*X[l],1.0*Y[l],1.0*X[l]*X[l],1.0*X[l]*Y[l],0,0,0};return;}
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
        t[x]=merge(t[x<<1],t[x<<1|1]);
    }
    void update(int x,int l,int r,int L,int R,int S,int T) {
        if(L<=l&&r<=R) {modify_x(x,l,r,S),modify_y(x,l,r,T);return;}
        pushdown(x,l,r);
        if(L<=mid) update(x<<1,l,mid,L,R,S,T);
        if(R>mid) update(x<<1|1,mid+1,r,L,R,S,T);
        t[x]=merge(t[x<<1],t[x<<1|1]);
    }
    void change(int x,int l,int r,int L,int R) {
        if(L<=l&&r<=R) {clear(x,l,r);return;}
        pushdown(x,l,r);
        if(L<=mid) change(x<<1,l,mid,L,R);
        if(R>mid) change(x<<1|1,mid+1,r,L,R);
        t[x]=merge(t[x<<1],t[x<<1|1]);
    }
    Node query(int x,int l,int r,int L,int R) {
        if(L<=l&&r<=R) return t[x];
        pushdown(x,l,r);
        if(R<=mid) return query(x<<1,l,mid,L,R);
        if(L>mid) return query(x<<1|1,mid+1,r,L,R);
        return merge(query(x<<1,l,mid,L,R),query(x<<1|1,mid+1,r,L,R));
    }
    #undef len
}T;

int main() {
    // freopen("2005.in","r",stdin);
    // freopen("2005.out","w",stdout);
    IN(n),IN(m);
    for(int i=1;i<=n;++i) IN(X[i]);
    for(int i=1;i<=n;++i) IN(Y[i]);
    T.build(1,1,n);
    while(m--) {
        int op,l,r,s,t;IN(op),IN(l),IN(r);
        if(op==1) {
            Node res=T.query(1,1,n,l,r);
            double len=1.0*(r-l+1);
            printf("%.10lf\n",(len*res.sxy-res.sx*res.sy)/(len*res.sx2-res.sx*res.sx));
        } else {
            IN(s),IN(t);
            if(op==3) T.change(1,1,n,l,r);
            T.update(1,1,n,l,r,s,t);
        }
    }
    return 0;
}
最后修改:2019 年 08 月 30 日 02 : 24 PM