87. 顏色的個數

0 Judge

Code: 0


顏色的個數

  • 卦長的弟弟最近在蓋一道牆,他把$n$塊磚頭放到地上用水泥連起來,從左到右編號依序是$1 \sim n$。接著就可以開始油漆了,卦長的弟弟總共有$64$種油漆,編號為$0 \sim 63$,他會有好幾次塗油漆的動作,每次他都會選三個數$x,y,c$,把第$x$塊磚頭和第$y$塊磚頭間的所有磚頭都塗成編號$c$油漆的顏色。
  • 在卦長的弟弟動工的時候,卦長會不時地來檢查,他每次會選兩個數$x,y$,算出第$x$塊磚頭和第$y$塊磚頭間有幾種顏色,但是每次都自己算太麻煩了,請你寫個程式幫幫卦長吧

輸入說明:

  • 輸入的第一行會有一個正整數$n$($1 \leq n \leq 1000000$),表示有$n$塊磚頭放在地上用水泥連起來,磚頭一開始全部都是編號$0$的顏色
  • 接著有一個整數$t$($0<t \leq 100000$),表示接下來按造順序有$t$個事件發生
  • 事件有兩種:
    • 1 x y c:卦長的弟弟將第$x$塊磚頭和第$y$塊磚頭間的所有磚頭都塗成編號$c$油漆的顏色,$0 \leq c \leq 63$,$1 \leq x \leq y \leq n$
    • 2 x y:卦長想算出第$x$塊磚頭和第$y$塊磚頭間有幾種顏色,$1 \leq x \leq y \leq n$

輸出說明

  • 對於每個2開頭的事件,請輸出有幾種顏色,記得換行

範例輸入:

5
20
1 1 1 1
1 2 2 2
1 3 3 3
1 4 4 4
1 5 5 5
2 1 5
2 1 1
2 2 2
2 3 3
2 4 4
2 5 5
1 1 2 2
1 3 5 1
2 1 5
2 1 4
2 1 3
1 2 4 9
2 2 4
2 1 4
2 3 4

範例輸出:

5
1
1
1
1
1
2
2
2
1
2
1

配分:

配分 限制
20% $1 \leq n \leq 100$
20% $1 \leq n \leq 1000$
60% 沒有限制
時限 350ms
記憶體 4276700 kb

Judge Setting

run-time limit: 350 ms
memory limit: 4276700 byte
測資數量: 0