Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Stick Game

By dhruba_1603088 · 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).

Input

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.

Output

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

Sample

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

Discussion

Statistics


61% Solution Ratio

DimmyTEarliest, Apr '20

DimmyTFastest, 0.2s

EgorKulikovLightest, 5.0 MB

NirjhorShortest, 1894B

Submit

Login to submit

Editorial

When a beauty number becomes replaced by another number in a range, after a few updates it will be s...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.