洛谷P3707 [SDOI2017]相关分析(线段树)

题目描述

Frank对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。

Frank不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮度和半径）是否存在某种关系。

现在Frank要分析参数XX 与YY 之间的关系。他有nn 组观测数据，第ii 组观测数据记录了x_ixi 和y_iyi 。他需要一下几种操作

1 L,RL,R ：

用直线拟合第LL 组到底RR 组观测数据。用\overline{x}x 表示这些观测数据中xx 的平均数，用\overline{y}y 表示这些观测数据中yy 的平均数，即

\overline{x}={1 \over R-L+1} \sum _{i=L} ^R x_ix=R−L+11∑i=LRxi

\overline{y}={1 \over R-L+1} \sum _{i=L} ^R y_iy=R−L+11∑i=LRyi

如果直线方程是y=ax+by=ax+b ，那么a,ba,b 应当这样计算：

a={\sum_{i=L} ^R (x_i-\overline{x})(y_i-\overline{y}) \over \sum _{i=L} ^R (x_i -\overline{x})^2}a=∑i=LR(xi−x)2∑i=LR(xi−x)(yi−y)

你需要帮助Frank计算aa 。

2 L,R,S,TL,R,S,T ：

Frank发现测量数据第LL 组到底RR 组数据有误差，对每个ii 满足L \leq i \leq RL≤i≤R ，x_ixi 需要加上SS ，y_iyi 需要加上TT 。

3 L,R,S,TL,R,S,T ：

Frank发现第LL 组到第RR 组数据需要修改，对于每个ii 满足L \leq i \leq RL≤i≤R ，x_ixi 需要修改为(S+i)(S+i) ，y_iyi 需要修改为(T+i)(T+i)。

输入输出格式

输入格式：

第一行两个数n,mn,m ，表示观测数据组数和操作次数。

接下来一行nn 个数，第ii 个数是x_ixi 。

接下来一行nn 个数，第ii 个数是y_iyi 。

接下来mm 行，表示操作，格式见题目描述。

输出格式：

对于每个1操作，输出一行，表示直线斜率aa 。选手输出与标准输出的绝对误差或相对误差不超过10^{-5}10−5 即为正确。

输入输出样例

输入样例#1：复制

输出样例#1：复制

1.0000000000

-1.5000000000

-0.6153846154

说明

对于20%的数据 1 \leq n,m \leq 10001≤n,m≤1000

另有20%的数据，没有3操作，且2操作中S=0S=0

另有30%的数据，没有3操作。

对于100%的数据，1 \leq n,m \leq 10^5,0 \leq |S|,|T| \leq 10^5,0 \leq |x_i|,|y_i| \leq 10^51≤n,m≤105,0≤∣S∣,∣T∣≤105,0≤∣xi∣,∣yi∣≤105

保证1操作不会出现分母为00 的情况。

时间限制：1s

空间限制：128MB

考场上：

线段树裸题—>100

wtf？为什么会有类似等差数列的东西？—>70

maya..被卡精度了QWQ—>40

思路很简单，把式子拆开，然后你就会发现只需要维护$x_i*y_i,x_i,y_i,x^2$的和

具体怎么维护懒得打了（麻烦。）

建议看这里的第一篇题解

https://www.luogu.org/problemnew/solution/P3707

// luogu-judger-enable-o2

#include<cstdio>

#include<queue>

#include<cstring>

#define int long long

#define ls k<<1

#define rs k<<1|1

#define INF 1e8+10

using namespace std;

const int MAXN=1e6+;

//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)

inline int read()

{

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

struct node

{

    int l,r,siz;

    double po;//x^2

    double mul;//xi*yi

    double sx,sy;//sigma

    double ax,ay;//add

    bool lazy;//memset

    node(){sx=-;sy=-;}

}T[MAXN];

struct Ans

{

    double sxiyi;

    double sxi,syi;

    double pox;

    Ans(){sxiyi=sxi=syi=pox=;}

};

Ans GetAns(int k)

{

    Ans rt;

    rt.sxiyi=T[k].mul;

    rt.sxi=T[k].sx;

    rt.syi=T[k].sy;

    rt.pox=T[k].po;

    return rt;

}

void update(int k)

{

    T[k].po=T[ls].po+T[rs].po;

    T[k].mul=T[ls].mul+T[rs].mul;

    T[k].sx=T[ls].sx+T[rs].sx;

    T[k].sy=T[ls].sy+T[rs].sy;

}

void Memset(int k)

{

    T[k].sx=(T[k].siz*(T[k].l+T[k].r))>>;

    T[k].sy=(T[k].siz*(T[k].l+T[k].r))>>;

    T[k].mul=(T[k].r*(T[k].r+)*(*T[k].r+))/-(T[k].l*(T[k].l-)*(*T[k].l-))/;

    T[k].po=(T[k].r*(T[k].r+)*(*T[k].r+))/-(T[k].l*(T[k].l-)*(*T[k].l-))/;

    T[k].ax=T[k].ay=;

    T[k].lazy=;

}

void Clear(int k,int S,int TT)

{

    T[k].po=T[k].po + 2.0*S*T[k].sx + T[k].siz*S*S;

    T[k].mul=T[k].mul + TT*T[k].sx + S*T[k].sy + T[k].siz*S*TT;

    T[k].sx=T[k].sx + T[k].siz*S;

    T[k].sy=T[k].sy + T[k].siz*TT;

    T[k].ax+=S;

    T[k].ay+=TT;

}

void pushdown(int k)

{

    if(T[k].lazy)

    {

        Memset(ls);

        Memset(rs);

        T[k].lazy=;

        return ;

    }

    int S=T[k].ax,TT=T[k].ay;

    Clear(ls,S,TT);

    Clear(rs,S,TT);

    T[k].ax=;

    T[k].ay=;

}

void Build(int ll,int rr,int k)

{

    T[k].l=ll;T[k].r=rr;

    T[k].siz=rr-ll+;

    if(ll==rr)

    {

        if(T[k].sx==-) {T[k].sx=read();return ;}

        T[k].sy=read();

        T[k].po=T[k].sx*T[k].sx;

        T[k].mul=T[k].sx*T[k].sy;

        return ;

    }

    int mid=ll+rr>>;

    Build(ll,mid,ls);

    Build(mid+,rr,rs);

    update(k);

}

Ans Query(int k,int ll,int rr)

{

    pushdown(k);

    Ans rt;

    if(ll<=T[k].l&&T[k].r<=rr)

    {

        rt=GetAns(k);

        return rt;

    }

    pushdown(k);

    int mid=T[k].l+T[k].r>>;

    if(ll<=mid)

    {

        pushdown(ls);

        Ans Q=Query(ls,ll,rr);

        rt.sxiyi+=Q.sxiyi;

        rt.sxi+=Q.sxi;

        rt.syi+=Q.syi;

        rt.pox+=Q.pox;

    }

    if(rr>mid)

    {

        pushdown(rs);

        Ans Q=Query(rs,ll,rr);

        rt.sxiyi+=Q.sxiyi;

        rt.sxi+=Q.sxi;

        rt.syi+=Q.syi;

        rt.pox+=Q.pox;

    }

    return rt;

}

void IntervalAdd(int k,int ll,int rr,int S,int TT)

{

    pushdown(k);

    if(ll<=T[k].l&&T[k].r<=rr)

    {

        Clear(k,S,TT);

        return ;

    }

    pushdown(k);

    int mid=T[k].l+T[k].r>>;

    if(ll<=mid) pushdown(ls),IntervalAdd(ls,ll,rr,S,TT);

    if(rr>mid)  pushdown(rs),IntervalAdd(rs,ll,rr,S,TT);

    update(k);

}

void IntervalMemset(int k,int ll,int rr)

{

    pushdown(k);

    if(ll<=T[k].l&&T[k].r<=rr)

    {

        Memset(k);

        return ;

    }

    pushdown(k);

    int mid=T[k].l+T[k].r>>;

    if(ll<=mid) pushdown(ls),IntervalMemset(ls,ll,rr);

    if(rr>mid)    pushdown(rs),IntervalMemset(rs,ll,rr);

    update(k);

}

main()

{

    #ifdef WIN32

    freopen("a.in","r",stdin);

    //freopen("c.out","w",stdout);

    #else

    #endif

    int N=read(),M=read();

    Build(,N,);

    Build(,N,);

    while(M--)

    {

        int opt=read();

        if(opt==)

        {

            int L=read(),R=read();

            Ans ans=Query(,L,R);

            double xba=(double)ans.sxi/(double)(R-L+);

            double yba=(double)ans.syi/(double)(R-L+);

            double up=ans.sxiyi-(double)yba*ans.sxi-(double)xba*ans.syi + (double)xba*yba*(R-L+);

            double down=ans.pox - (double)2.0*xba*ans.sxi + (double)xba*xba*(R-L+);

            printf("%.10lf\n",up/down);

        }

        else if(opt==)

        {

            int L=read(),R=read(),S=read(),TT=read();

            IntervalAdd(,L,R,S,TT);

        }

        else if(opt==)

        {

            int L=read(),R=read(),S=read(),TT=read();

            IntervalMemset(,L,R);

            IntervalAdd(,L,R,S,TT);

        }

    }

    return ;

}

稍微整理了一下

#include<cstdio>

#include<queue>

#include<cstring>

#define int long long

#define ls k<<1

#define rs k<<1|1

#define INF 1e8+10

using namespace std;

const int MAXN=1e6+;

//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)

inline int read()

{

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

struct node

{

    int l,r,siz;

    double po;//x^2

    double mul;//xi*yi

    double sx,sy;//sigma

    double ax,ay;//add

    bool lazy;//memset

    node(){sx=-;sy=-;}

}T[MAXN];

struct Ans

{

    double sxiyi;

    double sxi,syi;

    double pox;

    Ans(){sxiyi=sxi=syi=pox=;}

};

Ans GetAns(int k)

{

    Ans rt;

    rt.sxiyi=T[k].mul;

    rt.sxi=T[k].sx;

    rt.syi=T[k].sy;

    rt.pox=T[k].po;

    return rt;

}

void update(int k)

{

    T[k].po=T[ls].po+T[rs].po;

    T[k].mul=T[ls].mul+T[rs].mul;

    T[k].sx=T[ls].sx+T[rs].sx;

    T[k].sy=T[ls].sy+T[rs].sy;

}

void pushdown(int k)

{

    if(T[k].lazy)

    {

        T[ls].sx=(T[ls].siz*(T[ls].l+T[ls].r))>>;

        T[ls].sy=(T[ls].siz*(T[ls].l+T[ls].r))>>;

        T[ls].mul=(T[ls].r*(T[ls].r+)*(*T[ls].r+))/-(T[ls].l*(T[ls].l-)*(*T[ls].l-))/;

        T[ls].po=(T[ls].r*(T[ls].r+)*(*T[ls].r+))/-(T[ls].l*(T[ls].l-)*(*T[ls].l-))/;

        T[ls].ax=T[ls].ay=;

        T[ls].lazy=;

        T[rs].sx=(T[rs].siz*(T[rs].l+T[rs].r))>>;

        T[rs].sy=(T[rs].siz*(T[rs].l+T[rs].r))>>;

        T[rs].mul=(T[rs].r*(T[rs].r+)*(*T[rs].r+))/-(T[rs].l*(T[rs].l-)*(*T[rs].l-))/;

        T[rs].po=(T[rs].r*(T[rs].r+)*(*T[rs].r+))/-(T[rs].l*(T[rs].l-)*(*T[rs].l-))/;

        T[rs].ax=T[rs].ay=;

        T[rs].lazy=;

        T[k].lazy=;

        return ;

    }

    int S=T[k].ax,TT=T[k].ay;

    T[ls].po=T[ls].po+ 2.0*S*T[ls].sx + T[ls].siz*S*S;

    T[ls].mul=T[ls].mul + TT*T[ls].sx + S*T[ls].sy + T[ls].siz*S*TT;

    T[ls].sx=T[ls].sx + T[ls].siz*S;

    T[ls].sy=T[ls].sy + T[ls].siz*TT;

    T[ls].ax+=S;

    T[ls].ay+=TT;

    T[rs].po=T[rs].po+ 2.0*S*T[rs].sx + T[rs].siz*S*S;

    T[rs].mul=T[rs].mul + TT*T[rs].sx + S*T[rs].sy + T[rs].siz*S*TT;

    T[rs].sx=T[rs].sx + T[rs].siz*S;

    T[rs].sy=T[rs].sy + T[rs].siz*TT;

    T[rs].ax+=S;

    T[rs].ay+=TT;

    T[k].ax=;

    T[k].ay=;

}

void Build(int ll,int rr,int k)

{

    T[k].l=ll;T[k].r=rr;

    T[k].siz=rr-ll+;

    if(ll==rr)

    {

        if(T[k].sx==-) {T[k].sx=read();return ;}

        T[k].sy=read();

        T[k].po=T[k].sx*T[k].sx;

        T[k].mul=T[k].sx*T[k].sy;

        return ;

    }

    int mid=ll+rr>>;

    Build(ll,mid,ls);

    Build(mid+,rr,rs);

    update(k);

}

Ans Query(int k,int ll,int rr)

{

    pushdown(k);

    Ans rt;

    if(ll<=T[k].l&&T[k].r<=rr)

    {

        rt=GetAns(k);

        return rt;

    }

    pushdown(k);

    int mid=T[k].l+T[k].r>>;

    if(ll<=mid)

    {

        pushdown(ls);

        Ans Q=Query(ls,ll,rr);

        rt.sxiyi+=Q.sxiyi;

        rt.sxi+=Q.sxi;

        rt.syi+=Q.syi;

        rt.pox+=Q.pox;

    }

    if(rr>mid)

    {

        pushdown(rs);

        Ans Q=Query(rs,ll,rr);

        rt.sxiyi+=Q.sxiyi;

        rt.sxi+=Q.sxi;

        rt.syi+=Q.syi;

        rt.pox+=Q.pox;

    }

    return rt;

}

void IntervalAdd(int k,int ll,int rr,int S,int TT)

{

    pushdown(k);

    if(ll<=T[k].l&&T[k].r<=rr)

    {

        T[k].po=T[k].po + 2.0*S*T[k].sx + T[k].siz*S*S;

        T[k].mul=T[k].mul + TT*T[k].sx + S*T[k].sy + T[k].siz*S*TT;

        T[k].sx=T[k].sx + T[k].siz*S;

        T[k].sy=T[k].sy + T[k].siz*TT;

        T[k].ax+=S;

        T[k].ay+=TT;

        return ;

    }

    pushdown(k);

    int mid=T[k].l+T[k].r>>;

    if(ll<=mid) pushdown(ls),IntervalAdd(ls,ll,rr,S,TT);

    if(rr>mid)  pushdown(rs),IntervalAdd(rs,ll,rr,S,TT);

    update(k);

}

void IntervalMemset(int k,int ll,int rr)

{

    pushdown(k);

    if(ll<=T[k].l&&T[k].r<=rr)

    {

        T[k].sx=(T[k].siz*(T[k].l+T[k].r))>>;

        T[k].sy=(T[k].siz*(T[k].l+T[k].r))>>;

        T[k].mul=(T[k].r*(T[k].r+)*(*T[k].r+))/-(T[k].l*(T[k].l-)*(*T[k].l-))/;

        T[k].po=(T[k].r*(T[k].r+)*(*T[k].r+))/-(T[k].l*(T[k].l-)*(*T[k].l-))/;

        T[k].ax=T[k].ay=;

        T[k].lazy=;

        return ;

    }

    pushdown(k);

    int mid=T[k].l+T[k].r>>;

    if(ll<=mid) pushdown(ls),IntervalMemset(ls,ll,rr);

    if(rr>mid)    pushdown(rs),IntervalMemset(rs,ll,rr);

    update(k);

}

main()

{

    #ifdef WIN32

    freopen("a.in","r",stdin);

    freopen("c.out","w",stdout);

    #else

    #endif

    int N=read(),M=read();

    Build(,N,);

    Build(,N,);

    while(M--)

    {

        int opt=read();

        if(opt==)

        {

            int L=read(),R=read();

            Ans ans=Query(,L,R);

            double xba=(double)ans.sxi/(double)(R-L+);

            double yba=(double)ans.syi/(double)(R-L+);

            double up=ans.sxiyi-(double)yba*ans.sxi-(double)xba*ans.syi + (double)xba*yba*(R-L+);

            double down=ans.pox - (double)2.0*xba*ans.sxi + (double)xba*xba*(R-L+);

            printf("%.10lf\n",up/down);

        }

        else if(opt==)

        {

            int L=read(),R=read(),S=read(),TT=read();

            IntervalAdd(,L,R,S,TT);

        }

        else if(opt==)

        {

            int L=read(),R=read(),S=read(),TT=read();

            IntervalMemset(,L,R);

            IntervalAdd(,L,R,S,TT);

        }

    }

    return ;

}

巴特西

洛谷P3707 [SDOI2017]相关分析(线段树)

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章