Weirdtree

Time limit: 1.6s Memory limit: 512MB Input: Output:

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 NN trees, where the trees are indexed from 11 to NN. Each tree has a certain non-negative integer height. Azusa will then spend her time according to a schedule containing QQ entries, which can be of several types:

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

(Note that "between" is meant inclusively; e.g. 1;2;3;4;51; 2; 3; 4; 5 are "between" 11 and 55.)

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?

Interaction protocol

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 NN (the number of trees), QQ (the number of entries in the schedule), and an array hh, where h[i]h[i] is the height of tree ii, for 1iN1 \leq i \leq 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 ll and rr.

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,QN, Q, the sequence of NN initial heights, and the QQ 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 x1 \ l \ r \ k, \ 2 \ i \ x and 3 l r3 \ 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.

Restrictions

  • 1N,Q300 0001 \leq N, Q \leq 300 \ 000
  • It is guaranteed that the cut, magic and inspect functions will be called exactly QQ times in total.
  • 1iN1 \leq i \leq N
  • 0x,k,h[i]1 000 000 0000 \leq x, k, h[i] \leq 1 \ 000 \ 000 \ 000
  • 1lrN1 \leq l \leq r \leq N
# Points Restrictions
1 5 N1 000, Q1 000, k=1N \leq 1 \ 000, \ Q \leq 1 \ 000, \ k = 1
2 8 N80 000, Q80 000, k=1N \leq 80 \ 000, \ Q \leq 80 \ 000, \ k = 1
3 8 N1 000, Q1 000N \leq 1 \ 000, \ Q \leq 1 \ 000, there are no magic operations.
4 19 There are no magic operations.
5 10 l=1, r=Nl = 1, \ r = N
6 21 N80 000, Q80 000N \leq 80 \ 000, \ Q \leq 80 \ 000
7 29 No further restrictions.

Example

input

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

output

9
6
5
1005
4

Explanation

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

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

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

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

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

Log in or sign up to be able to send submissions!