#iq01gb. 矩形计算

时间限制：1 s       空间限制：256 MiB       标签： 离散化 莫队 二维莫队 BZOJ 

算法难度等级：6       思维难度等级：2       实现难度等级：5

题目描述

输入一个 $n \times m$ 的矩阵，矩阵的每一个元素都是一个整数，然后有 $q$ 个询问，每次询问一个子矩阵的权值。矩阵的权值是这样定义的，对于一个整数 $x$，如果它在该矩阵中出现了 $p$ 次，那么它给该矩阵的权值就贡献 $p^{2}$。

输入格式

第一行两个整数 $n,m$ 表示矩阵的规模。
接下来 $n$ 行每行 $m$ 个整数，表示这个矩阵的每个元素。 再下来一行一个整数 $q$，表示询问个数。 接下来 $q$ 行每行四个正整数 $x_{1},y_{1},x_{2},y_{2}$，询问以第 $x_{1}$ 行第 $y_{1}$ 列和第 $x_{2}$ 行第 $y_{2}$ 列的连线为对角线的子矩阵的权值。

输出格式

输出 $q$ 行每行一个整数回答对应询问。

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

8
4
38
1
8
12
27
4

数据规模与约定

对于 $100\%$ 数据，$1 \leq n,m \leq 200$，$0 \leq q \leq 10^5$，$|$ 矩阵元素大小 $| \leq 2 \times 10^{9}$。