271 . 照亮堅果樹

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

46.4% (13/28)

Tags

ioicamp ioicamp-2020

Description

今天你走在 NUT (National University of Taiwan) 的堅果大道上，你看到每棵堅果樹旁邊都有一盞路燈。而你，身為一個強迫症患者，看到眼前的 $N$ 盞燈，它們由左到右編號為 $1\sim N$ 排成一排卻都沒有亮起，使得你感到渾身不對勁。

為了解決這件事情，讓路過的行人都可以好好的欣賞堅果樹，你決定把所有的燈都點亮，但要一盞一盞手動去點亮實在是太慢了，對此你發現了這些燈的 $M$ 種連鎖反應，每種反應的形式大致如下：

  • $1\;v\;u$：若編號 $v$ 的燈亮起，則編號 $u$ 的燈也會跟著亮起。
  • $2\;v\;l\;r$：若編號 $v$ 的燈亮起，則編號 $[l,r]$ 區間內所有燈也都會跟著亮起。
  • $3\;v\;l\;r$：若編號 $[l,r]$ 區間內的燈有任何一盞亮起，則編號 $v$ 的燈也會跟著亮起。

請問你最少要手動點亮幾盞燈才可以把所有燈點亮？

Input Format

輸入首行有兩個正整數 $N,M$，代表燈的數量以及連鎖反應的數量。

接下來 $M$ 行，每行不外乎是其中一種連鎖反應的格式 $1\;v\;u$、$2\;v\;l\;r$、$3\;v\;l\;r$。

  • $1\le N,M\le 2\times 10^ 5$
  • $1 \leq v, u \leq N$
  • $1 \leq l \leq r \leq N$

Output Format

輸出在點亮所有燈的前提下，你最少要手動點亮幾盞燈。

Sample Input 1

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

Sample Output 1

2

Hints

Problem Source

IOICamp 2020 Day5 pH

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~58 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
15 3000 524288 65536 2
16 3000 524288 65536 2
17 3000 524288 65536 2
18 3000 524288 65536 2
19 3000 524288 65536 2
20 3000 524288 65536 2
21 3000 524288 65536 2
22 3000 524288 65536 2
23 3000 524288 65536 2
24 3000 524288 65536 2
25 3000 524288 65536 2
26 3000 524288 65536 2
27 3000 524288 65536 2
28 3000 524288 65536 2
29 3000 524288 65536 2
30 3000 524288 65536 2
31 3000 524288 65536 2
32 3000 524288 65536 2
33 3000 524288 65536 2
34 3000 524288 65536 2
35 3000 524288 65536 2
36 3000 524288 65536 2
37 3000 524288 65536 2
38 3000 524288 65536 2
39 3000 524288 65536 2
40 3000 524288 65536 2
41 3000 524288 65536 2
42 3000 524288 65536 2
43 3000 524288 65536 2
44 3000 524288 65536 2
45 3000 524288 65536 2
46 3000 524288 65536 2
47 3000 524288 65536 2
48 3000 524288 65536 2
49 3000 524288 65536 2
50 3000 524288 65536 2
51 3000 524288 65536 2
52 3000 524288 65536 2
53 3000 524288 65536 2
54 3000 524288 65536 2
55 3000 524288 65536 2
56 3000 524288 65536 2
57 3000 524288 65536 2
58 3000 524288 65536 2
Submit
Back to Top