传送
Time Limit : 8000/4000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
有一个 $ n $ 个节点 $ m $ 条边的无向图，对于一条边有四个参数 $ (a,b,l,r) $ ，表示这条边在 $ [l, r] $ 这些时间连接 $ (a,b) $ 。
有一个传送技能：如果在某时刻 $ u $ 和 $ v $ 在一个连通块里，可以从 $ u $ 传送到 $ v $ 。
小 A 初始在节点 $ 1 $ ，所以 小 A 想知道他能在 $[1, n]$ 中的哪些时间点能直接从 $ 1 $ 传送到节点 $ i $ ，请你帮帮他。
由于输出量可能过大，考虑简化输出，假设所有能从 $ 1 $ 到达 $ i $ 的时间点为 $ t_{i,1} \dots t_{i,k} $ ，定义 $ ans_i = \sum_{j=1}^{k} t_{i, j} $ ，你只需要输出一个 $ \oplus_{i=1}^{n} ans_i $ 即可，其中 $ \oplus $ 表示异或和。
有一个传送技能：如果在某时刻 $ u $ 和 $ v $ 在一个连通块里，可以从 $ u $ 传送到 $ v $ 。
小 A 初始在节点 $ 1 $ ，所以 小 A 想知道他能在 $[1, n]$ 中的哪些时间点能直接从 $ 1 $ 传送到节点 $ i $ ，请你帮帮他。
由于输出量可能过大，考虑简化输出，假设所有能从 $ 1 $ 到达 $ i $ 的时间点为 $ t_{i,1} \dots t_{i,k} $ ，定义 $ ans_i = \sum_{j=1}^{k} t_{i, j} $ ，你只需要输出一个 $ \oplus_{i=1}^{n} ans_i $ 即可，其中 $ \oplus $ 表示异或和。
Input
第一行输入 $ n,m $ 。
接下来 $ m $ 行，每行输入 $ a_i, b_i, l_i, r_i $ ，表示第 $ i $ 条边的属性。
$ 1 \leq n,m\leq 6 \times 10^5, 1 \leq a_i, b_i, l_i, r_i \leq n. $
接下来 $ m $ 行，每行输入 $ a_i, b_i, l_i, r_i $ ，表示第 $ i $ 条边的属性。
$ 1 \leq n,m\leq 6 \times 10^5, 1 \leq a_i, b_i, l_i, r_i \leq n. $
Output
输出一个数，表示答案。
Sample Input
4 5 1 3 3 4 2 1 3 4 4 3 1 3 2 4 2 2 4 3 3 3
Sample Output
9
Hint
答案分别是 10,7,7,3
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）