Another Contest 3 Problem 4 - Range Updates and Range Queries

Points: 15

Time limit: 0.25s

Memory limit: 256M

Problem types

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

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

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

Constraints

$1 \le N \le 10^6$ $1 \leq N \leq 10^{6}$

$1 \le Q \le 10^5$ $1 \leq Q \leq 10^{5}$

$1 \le l_i \le r_i \le N$ $1 \leq l_{i} \leq r_{i} \leq N$

$1 \le a_i \le 5$ $1 \leq a_{i} \leq 5$

Input Specification

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

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

Otherwise, the first integer in the line is $2$ $2$ , and then two integers follow, $l_i$ $l_{i}$ and $r_i$ $r_{i}$ , indicating a SUM operation.

Output Specification

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

Sample Input

Copy

Sample Output

Copy

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$ $1 \leq l_{i} \leq r_{i} \leq 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)$ $O (N Q \log N)$ , which is insufficient given the constraints (this is on the order of $10^{12}$ $10^{12}$ operations, give or take). If you are stumped, you can try reading the tutorial :)).