#P6942. [2018年5月雅礼集训]桥

    ID: 6773 传统题 1500ms 256MiB 尝试: 4 已通过: 2 难度: 7 上传者: 标签>难度分类提高+/省选-图论桥数据结构有序集合树状数组模拟与实现技巧增量维护添加哨兵CF2300

[2018年5月雅礼集训]桥

桥

Time Limit: 1.5s
Memory Limit: 256MB

Description

有一张2×N2\times N的网格图, 初始时其中有3N−23N-2 条边.

原题示意图

图1:N=3N=3 时的初始网格。坐标第一维为行(1或2),第二维为列(1到 NN),初始连接所有上下、左右相邻点。

现在给出MM次操作, 操作分为两类:

  • 1 x0 y0 x1 y1 加入 (x0,y0)(x_{0},y_{0}) 到 (x1,y1)(x_{1},y_{1}) 的边.

  • 2 x0 y0 x1 y1 删除 (x0,y0)(x_{0},y_{0}) 到 (x1,y1)(x_{1},y_{1}) 的边.

每次操作结束后输出图中桥边的数量, 这里的桥边指删除后会使联通块数量增加的边.

Input Format

输入数据第一行包含两个空格隔开的正整数N,MN,M.

接下来MM行, 每行描述一次操作.

Output Format

输出 M 行, 每行一个数, 表示当前图中桥边的数量.

Sample

样例0输入

4 8
2 1 3 2 3
2 1 2 2 2
2 1 4 2 4
1 1 2 2 2
1 1 3 2 3
2 1 1 2 1
1 1 4 2 4
2 2 2 2 3

样例0输出

0
0
7
4
2
4
2
4

Input1

见下发样例 /bridge/bridge1.in.

Output1

见下发样例 /bridge/bridge1.ans.

Constraints

对于 20% 的数据, N,M≤3000N,M\le 3000.

对于另外 40% 的数据, 只有删边操作.

对于 100% 的数据, NN, M≤200000M\le 200000, 加边和删边操作合法, ∣x0−x1∣+|x_{0}-x_{1}|+ ∣y0−y1∣=1|y_{0}-y_{1}|=1.