8592: BZOJ4592：[Shoi2015]脑洞治疗仪

曾经发明了自动刷题机的发明家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这段区间最大的脑洞有多大。 n,m <=200000，1<=l<=r<=n

输出格式

对于每个询问，输出一行一个整数，表示询问区间内最大连续脑洞区域有多大。

样例输入

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

提示

没有写明提示

题目来源

By 佚名上传