QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100

# 4918. 染色

统计

题目描述

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

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

  1. 给定三个整数 $ l, r, x $,表示把第 $ x $ 列的第 $ l $ 到第 $ r $ 个格子染黑。
  2. 给定三个整数 $ l, r, x $,表示把第 $ x $ 列的第 $ l $ 到第 $ r $ 个格子染白。
  3. 给定三个整数 $ l, r, v $,你需要把第 $ l $ 到第 $ r $ 行中美观程度最小的行的权值加上 $ v $,如有多行均为最小则对每行都加 $ v $。
  4. 给定两个整数 $ 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 $ 输出其答案。

样例一

input

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

output

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}$