#P2341. 山中的湖

    ID: 1390 传统题 1000ms 512MiB 尝试: 4 已通过: 1 难度: 8 上传者: 标签>数据结构计算几何排序与序列处理单调栈CF2500线段树模拟

山中的湖

山中的湖

题目描述

山的地面轮廓是一条折线。从左到右依次给出 NN 个拐点 (Xi,Yi)(X_i,Y_i),相邻拐点之间用线段连接。XiX_i 严格递增,两个端点的海拔为 00。下雨时,低洼处会形成湖。每个湖都蓄水到恰好开始溢出的高度,超出的水会流走。山上的总储水量是各湖横截面面积之和。

地面高度可能随消息而改变。每次改变后,都在新的地形上重新计算湖的蓄水状态。给定初始地形和收到的消息,请求出初始总储水量,并按顺序处理所有消息。

输入格式

第一行两个整数 N,MN,M,表示拐点数和消息数。

接下来 NN 行,第 ii 行两个整数 Xi,YiX_i,Y_i,表示第 ii 个拐点的坐标。

接下来 MM 行,每行是以下两种消息之一。

  • Survey x:测量横坐标 xx 处的水深和水面海拔。折线在该处的地面海拔由线段插值确定。
  • Descend i h:将第 ii 个拐点的海拔改为 hh,横坐标保持不变。拐点从 1 开始编号。hh 可以等于改动前的海拔。

输出格式

先输出一行,表示初始总储水量。之后每处理一条消息,输出一行。

  • 对 Survey,输出两个以空格分隔的数,依次表示水深和水面海拔。若测量处无水,则水深为 00,第二个数为该处的地面海拔。
  • 对 Descend,输出修改地形后的总储水量。

所有数均保留两位小数。评测时,每个输出数与参考值的绝对误差须不超过 0.0050010.005001。

数据范围

  • 3leNle1000003le Nle 100000,0leMle1000000le Mle 100000。
  • 0leX1<X2<cdots<XNle1060le X_1<X_2<cdots<X_Nle 10^6,0leYile1060le Y_ile 10^6,Y1=YN=0Y_1=Y_N=0。内部拐点的海拔也允许为 00。
  • Survey 的 xx 为实数,满足 X1lexleXNX_1le xle X_N。
  • Descend 的 i,hi,h 为整数,满足 1leileN1le ile N,0lehleYi0le hle Y_i。这里的 YiY_i 指当时的海拔。

样例

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

第一次测量时,横坐标 5.55.5 处的地面海拔为 4.754.75,湖面海拔为 5.005.00。第 44 个拐点的海拔降到 22 后,总储水量变为 4.004.00,而横坐标 5.55.5 处已经没有水。