No.3411 Range Clamp Sum
タグ : / 解いたユーザー数 28
作問者 :
AwashAmityOak
/ テスター :
ルク
yuusaan
It is guaranteed that AC can be obtained with PyPy3, but the use of compiled languages such as C++ is recommended.
Story
Awash misread ABC432E. Fortunately, he noticed the misreading within a few minutes and was able to get AC.
However, a few months later, it seems he has run into a situation where he must solve the problem as he had misread it...
Problem Statement
kazuppa, Awash, Yu~, and Ruku are preparing for a Christmas party. Awash is in charge of preparing the trees.
There is a row of $N$ Oak trees standing in a line. The $i$-th tree from the left is called tree $i$. The height of tree $i$ is $A_i$.
Awash plans to choose the trees in some contiguous interval of this row, even out their heights to some extent by grafting and pruning, and then decorate them. To determine the number of ornaments needed for the decoration, he wants to know the total height of the trees to be decorated.
Awash has not yet decided which interval of trees to decorate or how to even out the tree heights, so he wants a simulation program that can quickly compute the number of ornaments needed.
You are given $Q$ queries; process them in order. Each query is in one of the following formats.
1 x y: Cut down tree $x$ and plant a new tree of height $y$ in the same place. That is, change the value of $A_x$ to $y$.2 l r a b: For each $i$ satisfying $l \leq i \leq r$, even out the height of tree $i$ to be at least $a$ and at most $b$, and find the total height of the trees. That is, find the value of $\displaystyle \sum_{l \leq i \leq r} \max(a, \min(b, A_i))$. The evening out of trees to be at least $a$ and at most $b$ is not reflected in subsequent queries.
Input
$N\ Q$
$A_1\ A_2\ \dots\ A_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$
Here, $\mathrm{query}_q (1 \leq q \leq Q)$ represents the $q$-th query and is given in one of the following formats.
$1\ x\ y$
$2\ l\ r\ a\ b$
Constraints
- $1 \leq N \leq 10^5$
- $1 \leq Q \leq 10^5$
- $0 \leq A_i \leq 10^5$
-
For queries of type $1$:
- $1 \leq x \leq N$
- $0 \leq y \leq 10^5$
-
For queries of type $2$:
- $1 \leq l \leq r \leq N$
- $0 \leq a \leq b \leq 10^5$
- All input values are integers.
Output
Let $K$ be the number of queries of type $2$. Output $K$ lines. On the $q (1 \leq q \leq K)$-th line, output the answer to the $q$-th query of type $2$.
Sample
Sample 1
Input
6 5 1 4 6 3 2 5 2 2 5 3 5 1 2 7 1 4 0 2 4 5 4 9 2 2 3 2 5
Output
15 8 10
Initially, $A = (1, 4, 6, 3, 2, 5)$.
In the $1$-st query, we find the sum of the heights of trees $2$ through $5$ after evening them out to be at least $3$ and at most $5$. They are grafted and pruned as $(4, 6, 3, 2) \to (4, 5, 3, 3)$. Since $4 + 5 + 3 + 3 = 15$, output $15$.
In the $2$-nd query, tree $2$ is cut down and a new tree of height $7$ is planted. We get $A = (1, 7, 6, 3, 2, 5)$.
In the $3$-rd query, tree $4$ is cut down and a new tree of height $0$ is planted. We get $A = (1, 7, 6, 0, 2, 5)$.
In the $4$-th query, we find the sum of the heights of trees $4$ through $5$ after evening them out to be at least $4$ and at most $9$. They are grafted as $(0, 2) \to (4, 4)$. Since $4 + 4 = 8$, output $8$.
In the $5$-th query, we find the sum of the heights of trees $2$ through $3$ after evening them out to be at least $2$ and at most $5$. They are pruned as $(7, 6) \to (5, 5)$. Since $5 + 5 = 10$, output $10$.
Sample 2
Input
10 10 77 76 29 58 47 46 97 35 75 96 1 7 63 2 7 9 31 67 1 7 87 2 1 10 52 78 2 1 5 2 44 2 3 5 78 84 2 3 8 2 58 2 4 8 44 77 1 6 71 2 4 4 34 70
Output
165 650 205 234 273 272 58
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。