← 返回题目列表

Codeforces · 1912/G

G. 大城市圣彼得堡

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Great City Saint Petersburg - 原题 PDF 第 1 页
原题PDF第9页
可复制的 PDF 提取文本
ICPC 2023–2024, NERC – Northern Eurasia Finals
                       St. Petersburg, Novosibirsk, Astana, Kutaisi, December 13th, 2023
Problem G. Great City Saint Petersburg

    Time limit:        5 seconds
    Memory limit:     1024 megabytes

Saint Petersburg is the most beautiful city in the world unless it is raining. For the sake of this problem,
we will assume it is raining every single day.

One of the streets in Saint Petersburg has an unusual shape — it is a narrow stripe of n sections 1 meter
long each, where section i is at the height ai meters from the ground. The stripe is 1 meter deep and
bounded on the front and on the back by incredibly high buildings. Because of this, when it is raining,
a certain amount of rain will accumulate, unable to flow out of the street from either its leftmost or
rightmost end. Given the heights a1, a2,  . . . , an, you need to determine the amount of rain (in cubic
meters) which will accumulate on the street.

Moreover, your colleagues from the metropolitan construction company will be visiting for q days and on
day i they will be laying asphalt on all sections from li to ri inclusive, thus increasing the height of each
section li, li + 1, . . . , ri by 1 meter. You need to determine the total amount of water which accumulates
on the street before the construction works, and also after every single day of the construction works.

Input

The first line contains the number of blocks n and the number of construction events q (1 ≤n, q ≤2·105).
The second line contains n integers a1, a2, . . . , an (1 ≤ai ≤109) — the height of each section before all
the events. Each of the following q lines contains a pair of integers li, ri (1 ≤li ≤ri ≤n), denoting the
construction work from li to ri inclusive.

Output

Print q + 1 integers — the amount of water on the street before all updates, and also after every update.

Examples

             standard input                          standard output
 5 4                                     4
 3 2 1 2 3                               4
 1 5                                     1
 2 4                                     1
 1 2                                     3
 5 5

 7 3                                     2999999997
 1 1000000000 1 1 1 1000000000 1         2999999996
 1 3                                     2999999994
 4 5                                     2999999996
 5 7

Note

The picture illustrates the amount of water accumulating on the street in the first example.





                                         Page 9 of 15