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 $A$ of length $N$. Initially, $A[i] = i$ for each $i$ in the range $[1,N]$.

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

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

Input

In the first line of input, there will be two integers $N$ and $Q$ ($1 \le N \le 10^9$, $1 \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 $\texttt{1 L R V}$ or $\texttt{2 L R}$ ($1 \le L \le R \le N$, $1 \le V \le 10^5$).

Output

For each operation of the format $\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


Statistics

80% Solution Ratio

aminulEarliest, Dec '18

Sajjat004Fastest, 0.1s

SMAN2901Lightest, 8.0 MB

mahdi.hasnatShortest, 981B