Comet OJ

C1911 [Contest #14]转转的数据结构题

内存限制：256 MB 时间限制：4000 ms

题目描述

转转有一个长度为 $m$ 的整数序列 $c$，初值全是 $0$。

转转还有一个长度为 $n$ 的操作序列，第 $i$ 个操作用三元组 $(l_i,r_i,v_i)$ 描述，第 $i$ 个操作代表将 $c[l_i] \sim c[r_i]$ 赋值为 $v_i$。

现在，有 $q$ 个询问，第 $i$ 个询问有两个参数 $x_i$, $y_i$ ($x_i \le y_i$)。

第 $i$ 次询问请你回答依序执行第 $x_i$ 到 $y_i$ 这 $y_i - x_i + 1$ 个操作后，$c$ 序列中所有整数的和。每次询问开始时 $c$ 的所有数初值都会变回 $0$。

输入格式

第一行三个正整数 $n, m, q$，分别代表操作序列的长度、整数序列的长度以及询问的个数。

接下来还有 $n$ 行，当中的第 $i$ 行有 $3$ 个正整数 $l_i$,$r_i$,$v_i$，代表第 $i$ 个询问。

最后还有 $q$ 行，当中的第 $i$ 行有 $2$ 个正整数 $x_i, y_i$ ，表示第 $i$ 次询问。

  • $1 \le n,m,q \le 5 \times 10^5$

  • $1 \le l_i \le r_i \le m$

  • $0 \le v_i \le 2 \times 10^9$

  • $1 \le x_i \le y_i \le n$

输出

输出共 $q$ 行，每行一个整数， 第 $i$ 行的整数表示第 $i$ 次询问的答案。

样例

样例输入 1

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

样例输出 1

8
14
4

样例输入 2

10 10 10
1 5 20
5 7 7
3 6 8
1 6 20
1 7 14
5 6 5
9 9 18
5 10 5
1 9 6
1 5 19
1 10
5 5
7 10
4 8
1 9
1 6
6 7
7 10
2 6
1 4

样例输出 2

124
98
124
86
59
80
28
124
80
127

提示