染色 - 题目

你有一个 $ n $ 行 $ m $ 列的网格，每个格子可以被染黑或染白，初始每个格子均为白色。定义第 $ i $ 行的美观程度为最大的 $ x $ ，满足对于所有 $ 1 \le j \le x $，第 $ i $ 行的第 $ j $ 个格子的颜色是黑色。

你需要对这个网格执行 $ m $ 次操作。操作有以下四种：

给定三个整数 $ l, r, x $，表示把第 $ x $ 列的第 $ l $ 到第 $ r $ 个格子染黑。
给定三个整数 $ l, r, x $，表示把第 $ x $ 列的第 $ l $ 到第 $ r $ 个格子染白。
给定三个整数 $ l, r, v $，你需要把第 $ l $ 到第 $ r $ 行中美观程度最小的行的权值加上 $ v $，如有多行均为最小则对每行都加 $ v $。
给定两个整数 $ l, r $，你需要输出第 $ l $ 到第 $ r $ 行的权值之和，对 $ 2^{64} $ 取模。

每行初始权值为 $ 0 $。

第一行包含两个整数 $ n, m $。

接下来 $ m $ 行，每行第一个正整数 $ op_i $ 表示操作编号。

对于 $ op_i = 1 $ 或 $ op_i = 2 $，后面紧跟三个正整数 $ l_i, r_i, x_i $，表示执行上述对应操作。

对于 $ op_i = 3 $，后面紧跟三个整数 $ l_i, r_i, v_i $，表示执行上述对应操作。

对于 $ op_i = 4 $，后面紧跟两个整数 $ l_i, r_i $，表示询问这个区间的权值之和对 $ 2^{64} $ 取模的值。

若干行，对于每个 $ op_i = 4 $ 输出其答案。

1
1
2

对于 $100\%$ 的数据，$ 1 \le n, m \le 3 \times 10^5，1 \le l_i \le r_i \le n, 1 \le x_i \le \min(m, 1.5\times10^5), 0 \le v_i < 2^{64} $。

本题采用子任务捆绑测试。

$\text{subtask1}(10 pts)$：保证 $ 1 \le n, m \le 1000 $。

$\text{subtask2}(15 pts)$：保证 $ x_i = 1 $。

$\text{subtask3}(15 pts)$：保证 $ 1 \le x_i \le 10 $。

$\text{subtask4}(20 pts)$：保证 $ op_i = 3 $ 和 $ op_i = 4 $ 的操作一定出现在所有 $ op_i = 1 $ 和 $ op_i = 2 $ 的操作之后。

$\text{subtask5}(10 pts)$：保证 $ 1 \le n, m \le 40000 $。

$\text{subtask6}(30 pts)$：无特殊性质。

时间限制：$4\texttt{s}$

空间限制：$1024\texttt{MB}$

QOJ.ac