11431: CF102951 - D. Static Range Queries
[Creator : ]
Description
There is an array $a$ of length $10^9$, initially containing all zeroes.
First perform $N$ updates of the following form:
- Given integers $l, r$, and $v$, add $v$ to all values $a_l,a_{l+1},…,a_{r−1}$.
Then, answer $Q$ queries of the following form:
- Given integers $l$ and $r$, print the sum $a_l+a_{l+1}+⋯+a_{r−1}$.
Input
Line 1: The two space-separated integers $N, Q\ (1≤N,Q≤10^5)$
Lines $2..N+1$: Each line contains three space-separated integers $l, r$, and $v$, corresponding to an update $(0≤l<r≤10^9,\ v≤10^4)$.
Lines $N+2..N+Q+1$: Each line contains two space-separated integers $l$ and $r$, corresponding to a query $(0≤l<r≤10^9)$.
Output
Print $Q$ lines, the answers to the queries in the same order as given in the input.
Sample 1 Input
5 5
3 7 2
1 10 4
1 6 10
0 4 10
6 7 1
5 7
0 2
5 9
1 6
4 9
Sample 1 Output
23
34
31
106
47
Sample 2 Input
5 5
8 9 3
1 6 2
2 5 9
4 8 6
2 7 4
5 8
2 7
5 7
5 10
2 7
Sample 2 Output
28
73
22
31
73
Sample 3 Input
5 5
2 9 5
2 10 1
2 9 9
2 5 10
6 8 8
7 10
0 4
2 6
0 1
0 7
Sample 3 Output
39
50
90
0
113