#PU1258. USACO 2022 December Contest, Gold — Problem 2. Mountains

    ID: 1208 传统题 5000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec22来源:usaco.orgscoring:equal_test_cases单调栈二分答案

USACO 2022 December Contest, Gold — Problem 2. Mountains

USACO 2022 December Contest, Gold — Problem 2. Mountains

题目描述

Note: the time limit for this problem is 5s, 2.5 times the default. The memory limit is twice the default. There are NN (1≤N≤20001 \leq N \leq 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,…,hNh_1,h_2,\dots,h_N. For a mountain ii, you can see another mountain jj if there are no mountains strictly higher than the line of sight connecting the tops of mountain jj and ii. Formally, for two mountains i<ji < j, they can see each other if there is no kk such that i<k<ji < k < j and (k,hk)(k, h_k) is above the line segment connecting (i,hi)(i, h_i) and (j,hj)(j, h_j). There are QQ (1≤Q≤20001 \leq Q \leq 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 11 contains NN. Line 22 contains NN heights h1,h2,…,hNh_1,h_2,\dots,h_N (for each ii, 0≤hi≤1090 \leq h_i \leq 10^9). Line 33 contains QQ. Lines 44 to 3+Q3+Q contain xx, yy (1≤x≤N1 \leq x \leq N, 1≤y1 \leq y) where xx is the index of the mountain and yy is the amount the height increases by. It is guaranteed that the new height of the mountain is at most 10910^9.

输出格式

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

数据范围

Tests 2-5 satisfy N,Q≤100N, Q\le 100. Tests 6-11 satisfy Q≤10Q \leq 10. Tests 12-21 have no additional constraints. Problem credits: Joe Li and Larry Xing

样例

样例 1

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$.