U175513 刷的卡是别人家里的(加强版)(网格3)

最近 zxsoul 有亿点缺钱，他恰好他得到了 BS 的地图，所以他怂恿（~~强迫~~）他的弟弟 zxsure 去 BS 家将所有的银行卡都偷出来。 --- BS 实在看不下去了 于是把题目要过来进行了一波加强 这里是[原题目](https://www.luogu.com.cn/problem/U175404) --- 来自 BS 的提醒: 不要直接拿着原题的代码交了... 请阅读题目 ---

BS 的家是一个二维平面 $n\times n$，总所周知，BS 是一个技术 boy，他发明了一种机器人，可以在 $(x_1,y_1,x_2,y_2)$ 的范围内侦查是否有小偷。恰巧的是，zxsoul 是一名菜鸡，但他可以黑掉 BS 的机器人。不幸的是，他的弟弟 zxsure 笨手笨脚，每次行动只能拿一张卡片。现在已知每次需要偷的卡片位置 $(x,y)$，zxsoul 想知道每次行动需要黑多少机器人。这个问题对于 zxsoul 来说太难了，所以找了聪明的你来解决，如果你能解决，他决定将 $￥114514$ 的钱作为报酬送给你 --- BS 对这种行为进行了谴责 并在每个位置加派了若干机器人 ---

无

无

## 数据范围 对于 $20\%$ 的数据，有 $n\le 20，m\le 100$。 对于 $30\%$ 的数据，有 $n\le 5000，m\le 5000$。 对于 $100\%$ 的数据，有 $n\le 10^6，m\le 10^6$。 ## 这是一道模板题 上面是原题目里面的 对于这道题: ~~由于 BS 太懒了~~ 并没有测试点分治 所有的测试点数据范围均相同 且 满足 $n = 10^6, m = 10^6, 1 \leq cnt \leq 10^4$ ## 这依然是一道模板题