洛谷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=LR​xi​

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

如果直线方程是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: 

3 5
1 2 3
1 2 3
1 1 3
2 2 3 -3 2
1 1 2
3 1 2 2 1
1 1 3

输出样例#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+10;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';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=-43800000;sy=-43800000;}
}T[MAXN];
struct Ans
{
    double sxiyi;
    double sxi,syi;
    double pox;
    Ans(){sxiyi=sxi=syi=pox=0;}
};
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))>>1;
    T[k].sy=(T[k].siz*(T[k].l+T[k].r))>>1;
    T[k].mul=(T[k].r*(T[k].r+1)*(2*T[k].r+1))/6-(T[k].l*(T[k].l-1)*(2*T[k].l-1))/6;
    T[k].po=(T[k].r*(T[k].r+1)*(2*T[k].r+1))/6-(T[k].l*(T[k].l-1)*(2*T[k].l-1))/6;
    T[k].ax=T[k].ay=0;
    T[k].lazy=1;
}
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=0;
        return ;
    }
    int S=T[k].ax,TT=T[k].ay;
    Clear(ls,S,TT);
    Clear(rs,S,TT);
    T[k].ax=0;
    T[k].ay=0;
}
void Build(int ll,int rr,int k)
{
    T[k].l=ll;T[k].r=rr;
    T[k].siz=rr-ll+1;
    if(ll==rr)
    {
        if(T[k].sx==-43800000) {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>>1;
    Build(ll,mid,ls);
    Build(mid+1,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>>1;
    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>>1;
    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>>1;
    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(1,N,1);
    Build(1,N,1);
    while(M--)
    {
        int opt=read();
        if(opt==1)
        {
            int L=read(),R=read();
            Ans ans=Query(1,L,R);
            double xba=(double)ans.sxi/(double)(R-L+1);
            double yba=(double)ans.syi/(double)(R-L+1);
            double up=ans.sxiyi-(double)yba*ans.sxi-(double)xba*ans.syi + (double)xba*yba*(R-L+1);
            double down=ans.pox - (double)2.0*xba*ans.sxi + (double)xba*xba*(R-L+1);
            printf("%.10lf\n",up/down);
        }
        else if(opt==2)
        {
            int L=read(),R=read(),S=read(),TT=read();
            IntervalAdd(1,L,R,S,TT);
        }
        else if(opt==3)
        {
            int L=read(),R=read(),S=read(),TT=read();
            IntervalMemset(1,L,R);
            IntervalAdd(1,L,R,S,TT);
        }
    }        
    return 0;
}
#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+10;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';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=-43800000;sy=-43800000;}
}T[MAXN];
struct Ans
{
    double sxiyi;
    double sxi,syi;
    double pox;
    Ans(){sxiyi=sxi=syi=pox=0;}
};
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))>>1;
        T[ls].sy=(T[ls].siz*(T[ls].l+T[ls].r))>>1;
        T[ls].mul=(T[ls].r*(T[ls].r+1)*(2*T[ls].r+1))/6-(T[ls].l*(T[ls].l-1)*(2*T[ls].l-1))/6;
        T[ls].po=(T[ls].r*(T[ls].r+1)*(2*T[ls].r+1))/6-(T[ls].l*(T[ls].l-1)*(2*T[ls].l-1))/6;
        T[ls].ax=T[ls].ay=0;
        T[ls].lazy=1;
        T[rs].sx=(T[rs].siz*(T[rs].l+T[rs].r))>>1;
        T[rs].sy=(T[rs].siz*(T[rs].l+T[rs].r))>>1;
        T[rs].mul=(T[rs].r*(T[rs].r+1)*(2*T[rs].r+1))/6-(T[rs].l*(T[rs].l-1)*(2*T[rs].l-1))/6;
        T[rs].po=(T[rs].r*(T[rs].r+1)*(2*T[rs].r+1))/6-(T[rs].l*(T[rs].l-1)*(2*T[rs].l-1))/6;
        T[rs].ax=T[rs].ay=0;
        T[rs].lazy=1;
        T[k].lazy=0;
        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=0;
    T[k].ay=0;
}
void Build(int ll,int rr,int k)
{
    T[k].l=ll;T[k].r=rr;
    T[k].siz=rr-ll+1;
    if(ll==rr)
    {
        if(T[k].sx==-43800000) {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>>1;
    Build(ll,mid,ls);
    Build(mid+1,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>>1;
    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>>1;
    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))>>1;
        T[k].sy=(T[k].siz*(T[k].l+T[k].r))>>1;
        T[k].mul=(T[k].r*(T[k].r+1)*(2*T[k].r+1))/6-(T[k].l*(T[k].l-1)*(2*T[k].l-1))/6;
        T[k].po=(T[k].r*(T[k].r+1)*(2*T[k].r+1))/6-(T[k].l*(T[k].l-1)*(2*T[k].l-1))/6;
        T[k].ax=T[k].ay=0;
        T[k].lazy=1;
        return ;
    }
    pushdown(k);
    int mid=T[k].l+T[k].r>>1;
    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(1,N,1);
    Build(1,N,1);
    while(M--)
    {
        int opt=read();
        if(opt==1)
        {
            int L=read(),R=read();
            Ans ans=Query(1,L,R);
            double xba=(double)ans.sxi/(double)(R-L+1);
            double yba=(double)ans.syi/(double)(R-L+1);
            double up=ans.sxiyi-(double)yba*ans.sxi-(double)xba*ans.syi + (double)xba*yba*(R-L+1);
            double down=ans.pox - (double)2.0*xba*ans.sxi + (double)xba*xba*(R-L+1);
            printf("%.10lf\n",up/down);
        }
        else if(opt==2)
        {
            int L=read(),R=read(),S=read(),TT=read();
            IntervalAdd(1,L,R,S,TT);
        }
        else if(opt==3)
        {
            int L=read(),R=read(),S=read(),TT=read();
            IntervalMemset(1,L,R);
            IntervalAdd(1,L,R,S,TT);
        }
    }        
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏点滴积累

使用 opencv 将图片压缩到指定文件尺寸

前言 图片压缩应用很广泛,如生成缩略图等。前期我在进行图片处理的过程中碰到了一个问题,就是如何将图片压缩到指定尺寸,此处尺寸指的是生成图片文件的大小。 我使用 ...

95180
来自专栏大数据学习笔记

TensorFlow学习笔记:2、TensorFlow超简单入门程序

TensorFlow学习笔记:2、TensorFlow超简单入门程序 2.1 HelloWorld代码说明 import tensorflow as tf ...

27250
来自专栏机器学习算法与Python学习

不会用Photoshop抠图?Mask R-CNN助你一键“除”人

19430
来自专栏wOw的Android小站

[Tensorflow] Faster R-CNN 和自定义 VOC 数据集

看了pascal_voc.py代码,可以把代码的jpg拼接改成png,这样可以不做上一步.

1.7K20
来自专栏10km的专栏

SSD(Single Shot MultiBox Detector):ubuntu16安装及训练自己的数据集(VOC2007格式)过程记录

安装SSD # SSD代码clone到 caffe-ssd文件夹下 git clone --recursive https://github.com/weili...

51460
来自专栏深度学习与计算机视觉

手把手教你如何应用TF-Slim快速实现迁移学习

这是一篇以实践为主的入门文章,目的在于用尽量少的成本组织起来一套可以训练和测试自己的分类任务的代码,其中就会用到迁移学习,TF-Slim库的内容,所以我们分为下...

1.2K80
来自专栏一棹烟波

CUDA与OpenGL互操作

当处理较大数据量的时候,往往会用GPU进行运算,比如OpenGL或者CUDA。在实际的操作中,往往CUDA实现并行计算会比OpenGL更加方便,而OpenGL在...

302100
来自专栏人工智能LeadAI

pytorch入门教程 | 第四章:准备图片数据集

在训练神经网络之前,我们必须有数据,作为资深伸手党,必须知道以下几个数据提供源: 1 CIFAR-10 ? CIFAR-10图片样本截图 CIFAR-10是多...

1K80
来自专栏菩提树下的杨过

mxnet安装及NDArray初体验

一、mxnet安装 (以下均为mac环境) 有二种方式: 1.1 用conda安装 1 #创建gluon目录 2 mkdir gluon-tutorial...

30460
来自专栏生信技能树

【r<-ROC|包】分析与可视化ROC——plotROC、pROC

在【r<-绘图|ROC】ROC的计算与绘制这篇文章中我讲了ROC曲线的本质以及如何计算和绘制ROC曲线。注意,我这里谈到的ROC并未曾涉及机器学习模型的拟合与预...

22820

扫码关注云+社区

领取腾讯云代金券