P8904 [USACO22DEC] Mountains G

Along the edge of Farmer John’s farm, there are $N(1 \le N \le 2000)$ mountains arranged in a line at equal spacing. These mountains can be represented by a height array $h_1,h_2,\cdots,h_N$. For mountain $i$, mountain $j$ is visible if there is no mountain strictly higher than the line of sight connecting the peaks of mountains $j$ and $i$. Formally, for two mountains $i

The first line contains $N$. The second line contains $N$ heights $h_1,h_2,\cdots,h_N$ (for each $i$, $0 \le h_i \le 10^9$). The third line contains $Q$. Lines $4$ to $3+Q$ each contain $x,y(1 \le x \le N,1 \le y)$, where $x$ is the index of the mountain and $y$ is the amount by which its height increases. The input guarantees that the height of this mountain after the update does not exceed $10^9$.

Output $Q$ lines, each containing the number of unordered pairs of mountains that can see each other after the corresponding update.

### Sample 1 Explanation Initially, the following pairs of mountains can see each other: $(1,2)$, $(2,3)$, $(2,5)$, $(3,4)$, $(3,5)$, $(4,5)$, for a total of $6$ pairs. After the first update, the height of mountain $4$ becomes $4$. This does not block any existing visibility, but it makes mountain $4$ able to see mountain $2$, so the answer becomes $7$. After the second update, the height of mountain $1$ becomes $5$. This does not block any existing visibility, but it makes mountain $1$ able to see mountains $3$, $4$, and $5$, so the answer becomes $10$. After the third update, the height of mountain $3$ becomes $5$. This blocks mountain $1$ from seeing mountain $4$, and blocks mountain $2$ from seeing mountains $4$ and $5$. At the same time, since this mountain could already see all other mountains, it does not make it see more mountains, so the answer becomes $7$. ### Test Point Properties - Test points $2-5$ satisfy $N,Q \le 100$. - Test points $6-11$ satisfy $Q \le 10$. - Test points $12-21$ have no additional properties. Translated by ChatGPT 5