P3707 [SDOI2017]相关分析

    • 205通过
    • 855提交
  • 题目提供者 ElevenDimensions
  • 评测方式 云端评测
  • 标签 前缀和 块状链表,块状数组,分块 线段树 各省省选 2017 山东 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    现在Frank要分析参数$X$与$Y$之间的关系。他有$n$组观测数据,第$i$组观测数据记录了$x_i$和$y_i$。他需要一下几种操作

    • 1 $L,R$:

    用直线拟合第$L$组到底$R$组观测数据。用$\overline{x}$表示这些观测数据中$x$的平均数,用$\overline{y}$表示这些观测数据中$y$的平均数,即

    $\overline{x}={1 \over R-L+1} \sum _{i=L} ^R x_i$

    $\overline{y}={1 \over R-L+1} \sum _{i=L} ^R y_i$

    如果直线方程是$y=ax+b$,那么$a,b$应当这样计算:

    $a={\sum_{i=L} ^R (x_i-\overline{x})(y_i-\overline{y}) \over \sum _{i=L} ^R (x_i -\overline{x})^2}$

    你需要帮助Frank计算$a$。

    • 2 $L,R,S,T$:

    Frank发现测量数据第$L$组到底$R$组数据有误差,对每个$i$满足$L \leq i \leq R$,$x_i$需要加上$S$,$y_i$需要加上$T$。

    • 3 $L,R,S,T$:

    Frank发现第$L$组到第$R$组数据需要修改,对于每个$i$满足$L \leq i \leq R$,$x_i$需要修改为$(S+i)$,$y_i$需要修改为$(T+i)$。

    输入输出格式

    输入格式:

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

    接下来一行$n$个数,第$i$个数是$x_i$。

    接下来一行$n$个数,第$i$个数是$y_i$。

    接下来$m$行,表示操作,格式见题目描述。

    输出格式:

    对于每个1操作,输出一行,表示直线斜率$a$。选手输出与标准输出的绝对误差或相对误差不超过$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 1000$

    另有20%的数据,没有3操作,且2操作中$S=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^5$

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

    时间限制:1s

    空间限制:128MB

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。