Stick Game

dhruba_1603088 Criterion 2020 Round 6
Limits 1s, 256 MB

Shahwat has a stick that has n blocks that are indexed from 1 to n (from first to last). Each block has a beauty number written on it (Initially, it is the index number) and an abstract number which is invisible. Initially, all abstract numbers are 0. Then Shahwat will make k queries.

Each query can be of the following two types:

  • Type 1: He will give a range L, R, and an integer A. Here, beauty numbers of every block from L to R (inclusive) will be replaced by A. Suppose, one of the blocks from L to R (inclusive) had a beauty number B. After replacing, the beauty number of that block becomes A. After that, the abstract number of that block increases by the difference between A and B.
  • Type 2: He will ask the summation of the abstract numbers between L and R (inclusive).


The first line contains two integers n, k (1 ≤ n, k ≤ 2 * 105), denoting the number of blocks and the number of queries, respectively.

Each of the next k lines begins with an integer type (1 ≤ type ≤ 2), denoting the type of the query.

If the type of the query is 1, three space-separated integers L, R, A (1 ≤ L ≤ R ≤ n; 0 ≤ A ≤ 108) will follow.
If the type of the query is 2, two space-separated integers L, R (1 ≤ L ≤ R ≤ n) will follow.


For each query of type 2, print a line denoting the summation of abstract numbers.


10 6
1 1 5 3
2 2 7 
1 4 10 11
1 3 8 12
1 1 6 3
2 1 10


Login to submit.


61% Solution Ratio
DimmyTEarliest, Apr '20
DimmyTFastest, 0.2s
EgorKulikovLightest, 5.0 MB
NirjhorShortest, 1894B
Toph uses cookies. By continuing you agree to our Cookie Policy.