Practice on Toph

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

Just Another Range Query

By SMAN2901 · Limits 1s, 512 MB

This is another simple range query problem where you will perform some updates and answer some queries. Let's take an array AA of length NN. Initially, A[i]=iA[i] = i for each ii in the range [1,N][1,N].

You will have to perform QQ operations on this array. There will be two types of operations:

  • 1 L R V\texttt{1 L R V} - which means that you will have to subtract VV from all A[i]A[i] such that LiRL ≤ i ≤ R.
  • 2 L R\texttt{2 L R} - which means that you will have to print the sum of all A[i]A[i] such that LiRL ≤ i ≤ R.

Input

In the first line of input, there will be two integers NN and QQ (1N1091 \le N \le 10^9, 1Q1051 \le Q \le 10^5) which are the length of the array and number of operations to perform respectively.

Next Q lines will contain the description of the operations to perform in the format 1 L R V\texttt{1 L R V} or 2 L R\texttt{2 L R} (1LRN1 \le L \le R \le N, 1V1051 \le V \le 10^5).

Output

For each operation of the format 2 L R\texttt{2 L R}, print the answer of the query in a single line.

Sample

InputOutput
10 5
2 1 5
1 4 8 10
2 2 7
1 1 10 1
2 1 10
15
-13
-5

Discussion

Statistics


80% Solution Ratio

aminulEarliest, Dec '18

Sajjat004Fastest, 0.1s

SMAN2901Lightest, 8.0 MB

mahdi.hasnatShortest, 981B

Submit

Login to submit

Editorial

If we ignore input constraints, this is a classic segment tree problem. We need Nlog(N) space and ru...

Related Contests

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