P2122 还教室

    • 177通过
    • 476提交
  • 题目提供者 lin_toto 対立
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    还记得 NOIP 2012 提高组 Day2 中的借教室吗?时光飞逝,光阴荏苒,两年过去了,曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。

    题目描述

    在接受借教室请求的 $n$ 天中,第 $i$ 天剩余的教室为 $a_i$个。作为大学借教室服

    务的负责人,你需要完成如下三种操作共 $m$ 次:

    ① 第 $l$ 天到第 $r$ 天,每天被归还 $d$ 个教室。

    ② 询问第 $l$ 天到第 $r$ 天教室个数的平均数。

    ③ 询问第 $l$ 天到第 $r$ 天教室个数的方差。

    输入输出格式

    输入格式:

    第一行包括两个正整数 $n$ 和 $m$,其中 $n$ 为借教室的天数,$m$ 为操作次数。

    接下来一行,共包含 $n$ 个整数,第$i$个整数表示第 $i$ 天剩余教室数目为 $a_i$个。

    接下来 $m$ 行,每行的第一个整数为操作编号(只能为 $1$ 或 $2$ 或 $3$),接下来:

    包含两个正整数 $l$ 和 $r$,若操作编号为 $1$,则接下来再包含一个正整数 $d$。

    输出格式:

    对于每个操作 2 和操作 3,输出一个既约分数(分子与分母互质)表示询问的答案(详见样例)。若答案为 0,请输出“0/1”(不含引号)。

    输入输出样例

    输入样例#1: 复制
    5 4
    1 2 3 4 5
    1 1 2 3
    2 2 4
    3 2 4
    3 1 5
    输出样例#1: 复制
    4/1
    2/3
    14/25

    说明

    对于全部测试数据满足:$1 \leq l \leq r \leq n \leq 10^5, m\leq 10^5$,$0 \leq a_i \leq 10$,$1 \leq d \leq 3$,操作 $1$ 的数量不超过 $10\%$。

    注意:$a_i$和 $d$ 的范围很小及操作 $1$ 数量很少的原因是为了保证答案的分子不会很大,以防止答案的分子溢出 $64$ 位整数的范围,这与题目做法无关。

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