分数: 700 点
问题陈述
有一个无向图 N^2 顶点。最初,它没有边缘。对于每对整数 (i,\ j) 这样 0 \leq i,\ j < N,该图有一个对应的顶点,称为 (i,\ j).
你会得到 Q 查询,应按顺序处理。的 i-th 查询,它为您提供四个整数 a_i,\ b_i,\ c_i,\ d_i,如下。
- 对于每个 k (0 \leq k < N),在两个顶点之间添加一条边 ((a_i+k) \bmod N,\ (b_i+k) \bmod N) 和 ((c_i+k) \bmod N,\ (d_i+k) \bmod N)。然后,打印图中当前连接组件的数量。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq a_i,\ b_i,\ c_i,\ d_i < N
- (a_i,\ b_i) \neq (c_i,\ d_i)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 \vdots a_Q b_Q c_Q d_Q
输出
打印 Q 行。的 i第行应包含图中在 i第一个查询。
样本输入 1
3 3 0 0 1 2 2 0 0 0 1 1 2 2
示例输出 1
6 4 4
第一个查询在之间添加一条边 (0,\ 0),\ (1,\ 2)之间 (1,\ 1),\ (2,\ 0),以及之间 (2,\ 2),\ (0,\ 1),将连接组件的数量从 9 to 6.
示例输入 2
4 3 0 0 2 2 2 3 1 2 1 1 3 3
示例输出 2
14 11 11
查询后的图表可能并不简单。
示例输入 3
6 5 0 0 1 1 1 2 3 4 1 1 5 3 2 0 1 5 5 0 3 3
示例输出 3
31 27 21 21 19