LG#P13787. 地毯(加强版)

地毯(加强版)

P13787 地毯 加强版

题目描述

\hspace{15pt}在 n×nn \times n 的格子上有 mm 个地毯。

\hspace{15pt}给出这些地毯的信息,问每个点被多少个地毯覆盖。

\hspace{15pt}【名词解释】

∙ \hspace{23pt}\bullet\, 按位异或:a⊕ba \oplus b 表示把 aa 与 bb 写成二进制后逐位比较,两位相同为 00、不同为 11。例如 5⊕3=(101)2⊕(011)2=(110)2=65 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m \left(1 \leqq n \leqq 5000;\ 1 \leqq m \leqq 2 \times 10^5\right)$ 代表格子的边长与地毯的数量。

\hspace{15pt}此后 mm 行,第 ii 行输入四个整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2} \left(1 \leqq x_{i,1},x_{i,2},y_{i,1},y_{i,2} \leqq n\right)$ 代表一块地毯,左上角是 (xi,1,yi,1)(x_{i,1},y_{i,1}),右下角是 (xi,2,yi,2)(x_{i,2},y_{i,2})。

输出格式

\hspace{15pt}为了减少输出量,设 fi,jf_{i,j} 表示 (i,j)(i,j) 这个格子被多少个地毯覆盖,你只需要在一行上输出 ∑i=1n∑j=1n(i+j)⊕fi,j\sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)\oplus f_{i,j} 的值。注意这个值可能会超过 2312^{31}。

测试样例

5 3
2 2 3 3
3 3 5 5
1 2 1 4
146

数据范围与提示

\hspace{15pt}对于 50%50\% 的数据,n,m≦5000n,m \leqq 5000。