/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
N^2 頂点からなる無向グラフがあります。はじめ、グラフは辺を持ちません。 0 \leq i,\ j < N を満たす整数の組 (i,\ j) それぞれについて、それに対応する頂点がひとつ存在し、その頂点を (i,\ j) と呼びます。
Q 個のクエリが与えられます。i 番目のクエリでは 4 つの整数 a_i,\ b_i,\ c_i,\ d_i が与えられるので以下のように順番に処理してください。
- 各 k\ (0 \leq k < N) について、2 頂点 ((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
1 番目のクエリでは頂点 (0,\ 0),\ (1,\ 2) 間、(1,\ 1),\ (2,\ 0) 間、(2,\ 2),\ (0,\ 1) 間に辺が追加されます。これにより連結成分数は 9 から 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
Score : 700 points
Problem Statement
There is an undirected graph with N^2 vertices. Initially, it has no edges. For each pair of integers (i,\ j) such that 0 \leq i,\ j < N, the graph has a corresponding vertex called (i,\ j).
You will get Q queries, which should be processed in order. The i-th query, which gives you four integers a_i,\ b_i,\ c_i,\ d_i, is as follows.
- For each k (0 \leq k < N), add an edge between two vertices ((a_i+k) \bmod N,\ (b_i+k) \bmod N) and ((c_i+k) \bmod N,\ (d_i+k) \bmod N). Then, print the current number of connected components in the graph.
Constraints
- 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)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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
Output
Print Q lines. The i-th line should contain the number of connected components in the graph at the i-th query.
Sample Input 1
3 3 0 0 1 2 2 0 0 0 1 1 2 2
Sample Output 1
6 4 4
The first query adds an edge between (0,\ 0),\ (1,\ 2), between (1,\ 1),\ (2,\ 0), and between (2,\ 2),\ (0,\ 1), changing the number of connected components from 9 to 6.
Sample Input 2
4 3 0 0 2 2 2 3 1 2 1 1 3 3
Sample Output 2
14 11 11
The graph after queries may not be simple.
Sample Input 3
6 5 0 0 1 1 1 2 3 4 1 1 5 3 2 0 1 5 5 0 3 3
Sample Output 3
31 27 21 21 19