1976: [USACO 2022 December Contest Gold] Problem 2. Mountains

文件提交：无需freopen 内存限制：256 MB 时间限制：5.000 S
评测方式：普通裁判 命题人：
提交：1 解决：1

题目描述

There are N (1≤N≤2000) evenly spaced mountains in a row on the edge of Farmer John's farm. These can be expressed as an array of heights h1,h2,…,hN. For a mountain i, you can see another mountain j if there are no mountains strictly higher than the line of sight connecting the tops of mountain j and i. Formally, for two mountains i<j, they can see each other if there is no k such that i<k<j and (k,hk) is above the line segment connecting (i,hi) and (j,hj). There are Q (1≤Q≤2000) updates where the height of one mountain increases. Find the total number of unordered pairs of mountains that see each other after each update.

输入

Line 1 contains N.

Line 2 contains N heights h1,h2,…,hN (for each i, 0≤hi≤109).

Line 3 contains Q.

Lines 4 to 3+Q contain x, y (1≤x≤N, 1≤y) where x is the index of the mountain and y is the amount the height increases by. It is guaranteed that the new height of the mountain is at most 109.


输出

Q lines, with the total number of unordered pairs of mountains that see each other after each update.

样例输入 

5
2 4 3 1 5
3
4 3
1 3
3 2

样例输出 

7
10
7

提示

Initially, the following pairs of mountains can see each other: (1,2), (2,3), (2,5), (3,4), (3,5), (4,5), a total of 6.

After the first update, mountain 4 has a height of 4, which doesn't block any visibility but does make it so that 4 can now see 2, making the new answer 7.

After the second update, mountain 1 has a height of 5, which doesn't block any visibility but does make it so that 1 can now see 3, 4, and 5, making the new answer 10.

After the third update, mountain 3 has a height of 5, which blocks mountain 1 from seeing mountain 4, blocks mountain 2 from seeing mountains 4 and 5, and doesn't allow itself to see any more mountains since it can already see all of them, making the new answer 7.

SCORING:

  • Tests 2-5 satisfy N,Q≤100.
  • Tests 6-11 satisfy Q≤10.
  • Tests 12-21 have no additional constraints.

来源/分类

提交提交记录统计露一手!
codingfuture is powered by HUSTOJ, Theme by SYZOJ