TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4999
  • 問題
  • P4999「SHOI2015」脑洞治疗仪
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s 256m
    問題説明

    曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明:脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。

    为了简单起见,我们将大脑视作一个 01 序列。$1$ 代表这个位置的脑组织正常工作,$0$ 代表这是一块脑洞。

    1010001110

    脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出,将其中正常工作的脑组织填补在这块脑洞中。(所以脑洞治疗仪是脑洞的治疗仪?)

    例如,用上面第 $8$ 号位置到第 $10$ 号位置去修补第 $1$ 号位置到第 $4$ 号位置的脑洞,我们就会得到:

    1111001000

    如果再用第 $1$ 号位置到第 $4$ 号位置去修补第 $8$ 号位置到第 $10$ 号位置:

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

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

    1111000000
    这是因为如果新脑洞挖出来的脑组织不够多,脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。

    假定初始时 SHTSC 并没有脑洞,给出一些挖脑洞和脑洞治疗的操作序列,你需要即时回答 SHTSC 的问题:在大脑某个区间中最大的连续脑洞区域有多大。

    入力形式

    第一行两个整数 \(n\)\(m\),表示 SHTSC 的大脑可分为从 $1$ 到 \(n\) 编号的 \(n\) 个连续区域,有 \(m\) 个操作。

    以下 \(m\) 行每行是下列三种格式之一:

    • $0\quad l\quad r$:SHTSC 挖了一个范围为 \([l, r]\) 的脑洞。
    • $1\quad l_0\quad r_0\quad l_1\quad r_1$:SHTSC 进行了一次脑洞治疗,用从 \(l_0\)\(r_0\) 的脑组织修补 \(l_1\)\(r_1\) 的脑洞。
    • $2\quad l\quad r$:SHTSC 询问 \([l, r]\) 区间内最大的脑洞有多大。

    上述区间均在 \([1, 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

    ヒント

    对于 $20%$ 的数据,\(n, m \leq 100\)
    对于 $50%$ 的数据,\(n, m \leq 20000\)
    对于 $100%$ 的数据,\(n, m \leq 200000\)