P3707 [SDOI2017]相关分析

    • 157通过
    • 718提交
  • 题目提供者 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类违反进行处理。