P7030: 山
传统题
5.000s
时间限制
256MB
内存限制
5 提交
1 解决
【题目描述】
【题目描述】
**
注意：本题的时间限制为 5 秒，通常限制的 2.5 倍。内存限制是通常限制的两倍。**
沿着 Farmer John
的农场边缘有 N（1≤N≤2000
）座排成一行等间隔分布的山。这些山可以用一个高度数组 h1,h2,…,hN
表示。对于山 i，如果没有一座山严格高于连接山 j
和 i
山顶的视线，则可以看到山 j
。形式化地说，对于两座山 i<j，如果不存在 k
使得 i<k<j 并且 (k,hk) 高于联结 (i,hi) 和 (j,hj) 的线段，则这两座山之间互相可以看到对方。给定 Q（1≤Q≤2000
）次更新操作，每次更新增加一座山的高度。求每次更新后可以互相看到的山的无序对数。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
。
第 2
行包含 N 个高度 h1,h2,…,hN（对每一个 i
，有 0≤hi≤10
^9
）。
第 3
行包含 Q。
第 4
到 3+Q 行每行包含 x，y
（1≤x≤N
，1≤y1≤y
），其中 x
为山的编号，y 是山增加的高度。输入保证这座山更新后的高度不超过 10^9
。
【
输出格式】
（输出至终端 /
标准输出）：
输出 Q
行，包含每次更新后可以互相看到的山的无序对数。
【
输入样例】
：
5
2 4 3 1 5
3
4 3
1 3
3 2
【
输出样例】
：
7
10
7
【样例说明】
初始时，以下的山之间可以互相看到：(1,2)
，(2,3)
，(2,5)
，(3,4)
，(3,5)
，(4,5)
，共 6
对。
第一次更新后，山 4
的高度为 4，这不会阻挡现有的可见性，但使得山 4
现在可以看到山 2，从而使得答案变为 7
。
第二次更新后，山 1
的高度为 5，这不会阻挡现有的可见性，但使得山 1
现在可以看到山 3，4
和 5，从而使得答案变为 10
。
第三次更新后，山 3
的高度为 5，阻挡了山 1
看到山 4，阻挡了山 2
看到山 4 和 5，同时由于该山本就可以看到其他所有山，所以并没有使得该山看到更多的山，从而使得答案变为 7
。
【
测试点性质】
：
测试点 2-5
满足 N,Q≤100。
测试点 6-11
满足 Q≤10。
测试点 12-21
没有额外性质。