← 返回题目列表

AtCoder · arc141_e

E. 圆环上的滑动边缘

中文机器翻译题面 查看原题

分数: 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