#2041. 染色

    ID: 2041 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest762来源:qoj.ac数据:公开样例线段树

染色

染色

题目描述

标题: 染色 - Problem - QOJ.ac

#4918. 染色

Statistics

The problem was used in the following contests:

题目描述

你有一个 n 行 m 列的网格,每个格子可以被染黑或染白,初始每个格子均为白色。定义第 i 行的美观程度为最大的 x ,满足对于所有 1≤j≤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 行的权值之和,对 264 取模。

每行初始权值为 0。

输入格式

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

接下来 m 行,每行第一个正整数 opi 表示操作编号。

对于 opi=1 或 opi=2,后面紧跟三个正整数 li,ri,xi,表示执行上述对应操作。

对于 opi=3,后面紧跟三个整数 li,ri,vi,表示执行上述对应操作。

对于 opi=4,后面紧跟两个整数 li,ri,表示询问这个区间的权值之和对 264 取模的值。

输出格式

若干行,对于每个 opi=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≤n,m≤3×105,1≤li≤ri≤n,1≤xi≤min(m,1.5×105),0≤vi<264。

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

subtask1(10pts):保证 1≤n,m≤1000。

subtask2(15pts):保证 xi=1。

subtask3(15pts):保证 1≤xi≤10。

subtask4(20pts):保证 opi=3 和 opi=4 的操作一定出现在所有 opi=1 和 opi=2 的操作之后。

subtask5(10pts):保证 1≤n,m≤40000。

subtask6(30pts):无特殊性质。

时间限制:4s

空间限制:1024MB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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