1788: 万分之一的光(hard version)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：102
解决：14
题目描述
> 或许就像现在这样，孤独、寂寞。但我们依旧有着美好的明天。
> 不论这世界多糟糕，未来的我们，都会光芒万丈 。
小梦穿越到了魔都上海，这里高楼林立，灯光璀璨，小梦碰到了卷神zzh聚聚,小梦很崇拜zzh聚聚，但是zzh却给小梦出了个难题，要小梦数出现在城市里有多少路灯亮着，这可难住小梦了，你能帮帮她吗？
现在把城市的地图看做一个 n * n 网格，网格线就是道路。每个网格有一栋摩天大楼，每两个相邻的大楼中间有4栈路灯，但是只有两边大楼灯都亮着时这条路的路灯才亮。现在告诉你所有亮着灯的大楼的位置，共 k 座，可爱的小梦想知道一共有几盏路灯亮着，你能帮帮她吗？
两栋大楼 相邻 当且仅当有一条公共边。
本题题面与easy version完全一致，仅数据范围不同
> 不论这世界多糟糕，未来的我们，都会光芒万丈 。
小梦穿越到了魔都上海，这里高楼林立，灯光璀璨，小梦碰到了卷神zzh聚聚,小梦很崇拜zzh聚聚，但是zzh却给小梦出了个难题，要小梦数出现在城市里有多少路灯亮着，这可难住小梦了，你能帮帮她吗？
现在把城市的地图看做一个 n * n 网格，网格线就是道路。每个网格有一栋摩天大楼，每两个相邻的大楼中间有4栈路灯，但是只有两边大楼灯都亮着时这条路的路灯才亮。现在告诉你所有亮着灯的大楼的位置，共 k 座，可爱的小梦想知道一共有几盏路灯亮着，你能帮帮她吗？
两栋大楼 相邻 当且仅当有一条公共边。
本题题面与easy version完全一致，仅数据范围不同
输入
第一行两个整数 n,k ，表示网格边长和亮着灯的大楼的数量。
接下来 k 行每行两个整数 x,y ，表示大楼的坐标。
(1<=n,k<=105)
接下来 k 行每行两个整数 x,y ，表示大楼的坐标。
(1<=n,k<=105)
输出
一个整数，亮着的路灯的数量。
样例输入 复制
6 12
1 1
2 1
2 2
1 4
3 3
4 3
4 4
3 4
3 6
4 6
5 6
6 6样例输出 复制
36