[R46E]机器 - 代码源竞赛平台

时空限制

1S/512M

题目描述

你正在自动化车间操作机器生产糖果。车间里有一排糖果盒，编号为 $1$ 到 $n$，初始时每个盒子里的糖果数量均为 $0$。

车间里共有 $m$ 台机器，按编号 $1, 2, \dots, m$ 排列。机器共有两种类型：

1. 加法机器：给定参数 $l, r, x$，执行该机器会使糖果盒区间 $[l, r]$ 内的每个盒子增加 $x$ 个糖果。
2. 调用机器：给定参数 $l, r$，执行该机器会依次运行第 $l$ 台到第 $r$ 台机器的操作。保证对于第 $i$ 台机器，其调用的区间满足 $1 \le l \le r < i$，即机器只会调用编号比自己小的机器。

现在你收到了 $q$ 条指令，每条指令包含一个区间 $[l,r]$，表示依次运行第 $l$ 台到第 $r$ 台机器。

请计算在所有指令执行完毕后，每个糖果盒中最终的糖果数量。由于答案可能很大，请对 $10^9 + 7$ 取模后输出。

格式

输入格式

第一行包含三个整数 $n, m, q$，分别表示糖果盒数量、机器数量和指令数量。

接下来的 $m$ 行，每行描述一台机器：

• 首先是一个整数 $t$ ($t \in \{1, 2\}$)，表示机器类型。
• 若 $t=1$，接着输入三个整数 $l, r, x$，表示对糖果盒区间 $[l, r]$ 加上 $x$。
• 若 $t=2$，接着输入两个整数 $l, r$，表示调用第 $l$ 到第 $r$ 台机器。

接下来的 $q$ 行，每行包含两个整数 $l,r$，表示执行的一条指令。

输出格式

输出一行，包含 $n$ 个整数，表示每个糖果盒最终的糖果数量对 $10^9 + 7$ 取模后的结果。

样例

样例输入 #1

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

样例输出 #1

3 3 2 2 2

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n, m, q \le$	特殊性质
$1$	$30$	$2 \times 10^5$	仅包含类型 $1$ 机器，且所有指令满足 $l = r$
$2$	$70$		无

对于 $100\%$ 的数据，$1 \le n, m, q \le 2 \times 10^5$，$1 \le x \le 10^9$，对于所有类型 $1$ 机器：$1 \le l \le r \le n$；对于所有类型 $2$ 机器：$1 \le l \le r <$ 当前机器编号；对于所有指令：$1 \le l \leq r \le m$。