Another Contest 3 Problem 4 - Range Updates and Range Queries

View as PDF
Submit solution
Points: 15
Time limit: 0.25s
Memory limit: 256M
Problem types

You have an array of N integers, initialized all to zero to begin with. Support two operations.

INCREMENT l r a - For each index i between l and r, increase the ith element of the array by a \cdot (i-l+1).

SUM l r - Compute the sum of the integers between indices l and r, inclusive.

Constraints

1 \le N \le 10^6

1 \le Q \le 10^5

1 \le l_i \le r_i \le N

1 \le a_i \le 5

Input Specification

The first line contains two positive integers, N and Q.

The next Q lines each contain a sequence of positive integers. If the first integer in the line is 1, then three integers follow, l_i, r_i, and a_i, indicating an INCREMENT operation.

Otherwise, the first integer in the line is 2, and then two integers follow, l_i and r_i, indicating a SUM operation.

Output Specification

For each SUM operation, output on its own line the result of the query.

Sample Input

3 4
1 2 3 2
2 1 1
2 2 2
2 3 3

Sample Output

0
2
4

Comments


  • 0
    myl  commented on March 22, 2021, 2:47 p.m.

    I am assuming the array starts at index 0?


    • 2
      BalintR  commented on March 22, 2021, 2:57 p.m. ← edited

      1 \le l_i \le r_i \le N so no, the array starts at index 1.


  • 0
    AlanCCCL2S18  commented on Feb. 6, 2020, 11:51 p.m.

    Can anyone tell me why I'm TLEing on testcase 5? I know there's some sort of optimization but I don't know the specifics.


    • 8
      richardzhang  commented on Feb. 8, 2020, 1:08 a.m. ← edited

      Your time complexity is currently \mathcal{O}(NQ\log N), which is insufficient given the constraints (this is on the order of 10^{12} operations, give or take). If you are stumped, you can try reading the tutorial :)).