P2221 [HAOI2012]高速公路

    • 136通过
    • 358提交
  • 题目提供者xmyzwls 管理员
  • 标签 最大公约数,gcd 期望 线段树 各省省选 2012 河南 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    Y901高速公路是一条重要的交通纽带,政府部门建设初期的投入以及使用期间的养护费用都不低,因此政府在这条高速公路上设立了许多收费站。

    Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链,我们按照由西向东的顺序将收费站依次编号为1~N,从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。

    政府部门根据实际情况,会不定期地对连续路段的收费标准进行调整,根据政策涨价或降价。

    无聊的小A同学总喜欢研究一些稀奇古怪的问题,他开车在这条高速路上行驶时想到了这样一个问题:对于给定的l,r(l<r),在第l个到第r个收费站里等概率随机取出两个不同的收费站a和b,那么从a行驶到b将期望花费多少费用呢?

    输入输出格式

    输入格式:

    第一行2个正整数N,M,表示有N个收费站,M次调整或询问

    接下来M行,每行将出现以下两种形式中的一种

    C l r v 表示将第l个收费站到第r个收费站之间的所有道路的通行费全部增加v

    Q l r 表示对于给定的l,r,要求回答小A的问题

    所有C与Q操作中保证1<=l<r<=N

    输出格式:

    对于每次询问操作回答一行,输出一个既约分数

    若答案为整数a,输出a/1

    输入输出样例

    输入样例#1: 复制
    4 5
    C 1 4 2
    C 1 2 -1
    Q 1 2
    Q 2 4
    Q 1 4
    
    输出样例#1: 复制
    1/1
    8/3
    17/6
    

    说明

    所有C操作中的v的绝对值不超过10000

    在任何时刻任意道路的费用均为不超过10000的非负整数

    所有测试点的详细情况如下表所示

    Test N M

    1    =10    =10
    2    =100    =100
    3    =1000    =1000
    4    =10000    =10000
    5    =50000    =50000
    6    =60000    =60000
    7    =70000    =70000
    8    =80000    =80000
    9    =90000    =90000
    10    =100000    =100000
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。