시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB258832.000%

문제

Azusa, the witch of the highlands, has discovered a garden full of weird trees! Therefore, together with her friend, Laika, she decided to spend some time there taking care of the garden.

The garden can be viewed as a sequence of $N$ trees, where the trees are indexed from $1$ to $N$. Each tree has a certain non-negative integer height. Azusa will then spend her time according to a schedule containing $Q$ entries, which can be of several types:

  1. A tree cutting phase, characterised by three integers $l$, $r$, and $k$. In this phase, Azusa will spend the next $k$ days cutting trees. Each day she finds the tallest tree whose index is between $l$ and $r$ and decreases its height by $1$. In case there are several trees of this maximal height, she chooses the leftmost one. If the tallest tree has height $0$, then nothing happens on that day.
  2. A magic phase, characterised by two integers $i$ and $x$. In this phase, Azusa changes the tree with index $i$ so that it has height $x$.
  3. A tree inspection phase, characterised by two integers $l$ and $r$. In this phase, Azusa will find the sum of the heights of the trees with indices between $l$ and $r$.

(Note that “between” is meant inclusively; e.g. $1$, $2$, $3$, $4$, $5$ are “between” $1$ and $5$.)

Azusa is curious what the results of the tree inspection phases will be, and wants to know them without having to go through the entire schedule. Can you help her?

인터랙션 프로토콜

The contestant must implement the following four functions:

void initialise (int N, int Q, int h []);
void cut (int l, int r, int k);
void magic (int i, int x);
long long int inspect (int l, int r);

The function initialise is given $N$ (the number of trees), $Q$ (the number of entries in the schedule), and an array $h$, where $h[i]$ is the height of tree $i$, for $1 ≤ i ≤ N$. This function is called by the committee’s code exactly once, before any of the other three functions are called. The cut, magic and inspect functions represent tree cutting, magic and tree inspecting phases respectively, and are characterised by their respective parameters. The contestant’s implementation of the inspect function must return the sum of the heights of the trees with indices between $l$ and $r$.

The contestant should not implement the main function. This will be implemented in the committee’s grader.cpp file; you will be given a sample grader.cpp in the attachments. Our main function will read $N$, $Q$, the sequence of $N$ initial heights, and the $Q$ schedule entries. The three types of schedule entries (cut(l, r, k), magic(i, x) and inspect(l, r)) are encoded as 1 l r k, 2 i x and 3 l r respectively. This is the input format that will be used in the examples below.

Note that the contestant is allowed to use global variables, additional functions, methods and classes.

제한

  • $1 ≤ N, Q ≤ 300\,000$
  • It is guaranteed that the cut, magic and inspect functions will be called exactly $Q$ times in total.
  • $1 ≤ i ≤ N$
  • $0 ≤ x, k, h[i] ≤ 1\,000\,000\,000$
  • $1 ≤ l ≤ r ≤ N$

서브태스크

번호배점제한
15

$N ≤ 1\,000$, $Q ≤ 1\,000$, $k = 1$

28

$N ≤ 80\,000$, $Q ≤ 80\,000$, $k = 1$

38

$N ≤ 1\,000$, $Q ≤ 1\,000$, there are no magic operations.

419

There are no magic operations.

510

$l = 1$, $r = N$

621

$N ≤ 80\,000$, $Q ≤ 80\,000$

729

No further restrictions

예제 입력 1

6 10
1 2 3 1 2 3
1 1 6 3
3 1 6
1 1 3 3
3 1 6
1 1 3 1000
3 1 6
2 1 1000
3 1 6
1 1 3 999
3 1 5

예제 출력 1

9
6
5
1005
4

힌트

In the first phase, after each of the $3$ days of tree cutting, the heights of the trees are $1, 2, 2, 1, 2, 3$; $1, 2, 2, 1, 2, 2$; and $1, 1, 2, 1, 2, 2$. The sum of these values is $9$, which is the answer to the inspection in the second phase.

In the third phase, after each of the $3$ days of tree cutting, the heights of the trees are $1, 1, 1, 1, 2, 2$; $0, 1, 1, 1, 2, 2$; and $0, 0, 1, 1, 2, 2$. The sum of these values is $6$, which is the answer to the inspection in the fourth phase.

In the fifth phase, after each of the $1000$ days of tree cutting, the heights of the trees are $0, 0, 0, 1, 2, 2$. This is because a tree with height $0$ cannot be cut. The sum of these values is $5$, which is the answer to the inspection in the sixth phase.

In the seventh phase, the first tree is grown to height $1000$, giving us tree heights $1000, 0, 0, 1, 2, 2$. The sum of these values is $1005$, which is the answer to the inspection in the eighth phase.

In the ninth phase, each of the $999$ days of tree cutting reduces the height of the first tree by $1$. This gives us tree heights $1, 0, 0, 1, 2, 2$ at the end of the phase. The sum of the first five of these values is $4$, which is the answer to the inspection in the tenth and final phase.

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.