BZOJ 1568: [JSOI2008]Blue Mary开公司

正文索引 [隐藏]

Description

Input
第一行 :一个整数N ,表示方案和询问的总数。 接下来N行,每行开头一个单词“Query”或“Project”。 若单词为Query,则后接一个整数T,表示Blue Mary询问第T天的最大收益。 若单词为Project,则后接两个实数S,P,表示该种设计方案第一天的收益S,以及以后每天比上一天多出的收益P。
Output
对于每一个Query,输出一个整数,表示询问的答案,并精确到整百元(以百元为单位,例如:该天最大收益为210或290时,均应该输出2)。

Sample Input

5
Query 2
Project 0 100
Query 2
Project 280 10
Query 2
Project 290 10
Query 2

Sample Output

1
2
3

HINT

约定:
1 <= N <= 100000
1 <= T <=50000
0 < P < 100,| S | <= 10^6
提示:本题读写数据量可能相当巨大,请选手注意选择高效的文件读写方式。

题解

Orz考前手感差QAQ!写个线段树也写成了SB、、、
这道题目我们可以发现任意每次加入的Project都是在一段连续的区间里最优的,节点中只要记录序列开头s和公差d,然后更新就可以了。

代码