OI Problems   关于

#iq01gb. 矩形计算

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

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


本题来源于:BZOJ 2639

题目描述

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

输入格式

第一行两个整数 n,mn,m 表示矩阵的规模。
接下来 nn 行每行 mm 个整数,表示这个矩阵的每个元素。 再下来一行一个整数 qq,表示询问个数。 接下来 qq 行每行四个正整数 x1,y1,x2,y2x_{1},y_{1},x_{2},y_{2},询问以第 x1x_{1} 行第 y1y_{1} 列和第 x2x_{2} 行第 y2y_{2} 列的连线为对角线的子矩阵的权值。

输出格式

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

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%100\% 数据,1n,m2001 \leq n,m \leq 2000q1050 \leq q \leq 10^5| 矩阵元素大小 2×109| \leq 2 \times 10^{9}