#2307. 脑洞治疗仪

    ID: 2307 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>PROV赛事:contest2726来源:qoj.ac数据:公开样例线段树

脑洞治疗仪

脑洞治疗仪

题目描述

第4页 题二: 脑洞治疗仪(brainhole.pas / c / cpp ) 【问题描述】曾经发明了自动刷题机的发明家SHTSC 又公开了他的新发明:脑洞治疗仪— —一种可以治疗他因为发明而日益增大的脑洞的神秘装置。 为了简单起见,我们将大脑视作一个01 序列。1 代表这个位置的脑组织正常工作,0 代表这是一块脑洞。 1 0 1 0 0 0 1 1 1 0 脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出,将其中正常工 作的脑组织填补在这块脑洞中。 例如,用上面第8 号位置到第10 号位置去修补第1 号位置到第4 号位置的脑洞。我们 就会得到: 1 1 1 1 0 0 1 0 0 0 如果再用第1 号位置到第4 号位置去修补第8 号位置到第10 号位置: 0 0 0 0 0 0 1 1 1 1

这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。

如果再用第7 号位置到第10 号位置去填补第1 号位置到第6 号位置: 1 1 1 1 0 0 0 0 0 0

这是因为如果新脑洞挖出来的脑组织不够多,脑洞治疗仪仅会尽量填补位置比较靠前的 脑洞。假定初始时SHTSC 并没有脑洞,给出一些挖脑洞和脑洞治疗的操作序列,你需要即 时回答SHTSC 的问题:在大脑某个区间中最大的连续脑洞区域有多大。 【输入文件】第一行两个整数n,m。表示SHTSC 的大脑可分为从1 到n 编号的n 个连续 区域。有m 个操作。 以下m 行每行是下列三种格式之一。 0 l r :SHTSC 挖了一个从l 到r 的脑洞。 1 l0 r0 l1 r2 :SHTSC 进行了一次脑洞治疗,用从l0 到r0 的脑组织修补l1 到r1 的脑洞。 2 l r :SHTSC 询问l 到r 这段区间最大的脑洞有多大。 【输出文件】对于每个询问,输出一行一个整数,表示询问区间内最大连续脑洞区域有多大。 【输入输出样例】 brainhole1.in brainhole1.out 10 10 0 2 2 0 4 6 0 10 10 2 1 10 1 8 10 1 4 2 1 10 1 1 4 8 10 2 1 10 1 7 10 1 6 2 1 10 3 3 6 6 brainhole2.in brainhole2.out 10 8 0 1 2 2 3 4 0 2 2

第5页 2 1 2 0 4 5 0 10 10 2 1 5 1 1 5 10 10 2 1 5 5 【样例说明】样例1: 2 1 10 / ans = 3 1 0 1 0 0 0 1 1 1 0 2 1 10 / ans = 3 1 1 1 1 0 0 1 0 0 0 2 1 10 / ans = 6 0 0 0 0 0 0 1 1 1 1 2 1 10 / ans = 6 1 1 1 1 0 0 0 0 0 0 样例2: 2 3 4 / ans = 0 0 0 1 1 1 1 1 1 1 1 2 1 2 / ans = 2 0 0 1 1 1 1 1 1 1 1 2 1 5 / ans = 2 0 0 1 0 0 1 1 1 1 0 2 1 5 / ans = 5 0 0 0 0 0 1 1 1 1 1 【数据规模】对于20%的数据:n,m<= 100。 对于50%的数据:n,m<= 20000。其中询问操作不超过100 次。 对于100%的数据:n,m<=200000,1<=l<=r<=n。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

10 10
0 2 2
0 4 6
0 10 10
2 1 10
1 8 10 1 4
2 1 10
1 1 4 8 10
2 1 10
1 7 10 1 6
2 1 10
3
3
6
6