#P2341. 山中的湖
山中的湖
山中的湖
题目描述
山的地面轮廓是一条折线。从左到右依次给出 个拐点 ,相邻拐点之间用线段连接。 严格递增,两个端点的海拔为 。下雨时,低洼处会形成湖。每个湖都蓄水到恰好开始溢出的高度,超出的水会流走。山上的总储水量是各湖横截面面积之和。
地面高度可能随消息而改变。每次改变后,都在新的地形上重新计算湖的蓄水状态。给定初始地形和收到的消息,请求出初始总储水量,并按顺序处理所有消息。
输入格式
第一行两个整数 ,表示拐点数和消息数。
接下来 行,第 行两个整数 ,表示第 个拐点的坐标。
接下来 行,每行是以下两种消息之一。
Survey x:测量横坐标 处的水深和水面海拔。折线在该处的地面海拔由线段插值确定。Descend i h:将第 个拐点的海拔改为 ,横坐标保持不变。拐点从 1 开始编号。 可以等于改动前的海拔。
输出格式
先输出一行,表示初始总储水量。之后每处理一条消息,输出一行。
- 对
Survey,输出两个以空格分隔的数,依次表示水深和水面海拔。若测量处无水,则水深为 ,第二个数为该处的地面海拔。 - 对
Descend,输出修改地形后的总储水量。
所有数均保留两位小数。评测时,每个输出数与参考值的绝对误差须不超过 。
数据范围
- ,。
- ,,。内部拐点的海拔也允许为 。
Survey的 为实数,满足 。Descend的 为整数,满足 ,。这里的 指当时的海拔。
样例
7 3
0 0
1 4
2 2
3 6
4 4
6 5
8 0
Survey 5.5
Descend 4 2
Survey 5.5
2.75
0.25 5.00
4.00
0.00 4.75
第一次测量时,横坐标 处的地面海拔为 ,湖面海拔为 。第 个拐点的海拔降到 后,总储水量变为 ,而横坐标 处已经没有水。