P4254 [JSOI2008]Blue Mary开公司

    • 150通过
    • 425提交
  • 题目提供者 KSkun
  • 评测方式 云端评测
  • 标签 线段树 递归 各省省选 2008 江苏
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    Blue Mary 最近在筹备开一家自己的网络公司。由于他缺乏经济头脑,所以先后聘请了若干个金融顾问为他设计经营方案。

    题目描述

    万事开头难,经营公司更是如此。开始的收益往往是很低的,不过随着时间的增长会慢慢变好。也就是说,对于一个金融顾问 $i$,他设计的经营方案中,每天的收益都比前一天高,并且均增长一个相同的量 $P_i$。

    由于金融顾问的工作效率不高,所以在特定的时间,Blue Mary 只能根据他已经得到的经营方案来估算某一时间的最大收益。由于 Blue Mary 是很没有经济头脑的,所以他在估算每天的最佳获益时完全不会考虑之前的情况,而是直接从所有金融顾问的方案中选择一个在当天获益最大的方案的当天的获益值,例如:

    有如下两个金融顾问分别对前四天的收益方案做了设计:

    第一天 第二天 第三天 第四天 $P_i$
    顾问 1 1 5 9 13 4
    顾问 2 2 5 8 11 3

    在第一天,Blue Mary认为最大收益是 2(使用顾问 2 的方案),而在第三天和第四天,他认为最大收益分别是 9 和 13(使用顾问 1 的方案)。而他认为前四天的最大收益是:

    $2 + 5 + 9 + 13 = 29$

    现在你作为 Blue Mary 公司的副总经理,会不时收到金融顾问的设计方案,也需要随时回答 Blue Mary 对某天的“最大收益”的询问(这里的“最大收益”是按照 Blue Mary 的计算方法)。一开始没有收到任何方案时,你可以认为每天的最大收益值是 0。下面是一组收到方案和回答询问的例子:

    询问 2
    回答 0
    收到方案:0 1 2 3 4 5 ……
    询问 2
    回答 1
    收到方案:2 2.1 2.2 2.3 2.4 ……
    询问 2
    回答 2.1

    输入输出格式

    输入格式:

    第一行 :一个整数 $N$ ,表示方案和询问的总数。

    接下来 $N$ 行,每行开头一个单词QueryProject

    若单词为Query,则后接一个整数 $T$,表示 Blue Mary 询问第 $T$ 天的最大收益。

    若单词为Project,则后接两个实数 $S$,$P$,表示该种设计方案第一天的收益 $S$,以及以后每天比上一天多出的收益 $P$。

    输出格式:

    对于每一个Query,输出一个整数,表示询问的答案,并精确到整百元(以百元为单位,例如:该天最大收益为 210 或 290 时,均应该输出 2)。没有方案时回答询问要输出 0。

    输入输出样例

    输入样例#1: 复制
    10
    Project 5.10200 0.65000
    Project 2.76200 1.43000
    Query 4
    Query 2
    Project 3.80200 1.17000
    Query 2
    Query 3
    Query 1
    Project 4.58200 0.91000
    Project 5.36200 0.39000
    输出样例#1: 复制
    0
    0
    0
    0
    0

    说明

    数据范围:

    $1 \leq N \leq 100000, 1 \leq T \leq 50000, 0 < P < 100, |S| \leq 10^5$

    提示:

    本题读写数据量可能相当巨大,请选手注意选择高效的文件读写方式。

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