UOJ Logo LFYZ Online Judge

LFYZOJ

#336. 【2018 国庆雅礼 NOIP 培训】D2T2 蔬菜(vegetable)

统计

问题描述

小 C 在家中开垦了一块菜地, 可以抽象成一个 $r × c$ 大小的矩形区域, 菜地的每个位置都种着一种蔬菜. 秋天到了, 小 C 家的菜地丰收了.

小 C 拟定了 $q$ 种采摘蔬菜的计划, 计划采摘区域是菜地的一个子矩形, 你需要帮助他计算每种计划的美味度, 美味度等于每种蔬菜在采摘区域出现 次数的平方和.

输入格式

第一行三个正整数 $r, c, q$.

接下来 $r$ 行每行 $c$ 个正整数, 第 $i + 1$ 行第 $j$ 个数为 $a_{ij}$ , 表示每个位 置的蔬菜种类.

接下来 $q$ 行, 每行 4 个正整数 $ x0, y0, x1, y1 $ 表示采摘区域的左上角和 右下角的位置.

输出格式

输出 $q$ 行, 每行一个整数, 第 $i$ 行的数表示第$ i$ 组采摘计划的答案.

样例

input

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

output

8
4
38
1
8
12
27
4

数据范围与约定

对于 $100\%$ 的数据, $r, c ≤ 200, q ≤ 100000, a_{ij} ≤ 10^9$

$• Subtask 1 (23pts): r, c ≤ 100, q ≤ 1000.$

$• Subtask 2 (15pts): r, c ≤ 100, q ≤ 10000.$

$• Subtask 3 (17pts): r, c ≤ 200, q ≤ 50000.$

$• Subtask 4 (20pts): $蔬菜种类数不超过 200

$• Subtask 5 (25pts): $无特殊限制

时间限制: $1\mathrm{s}$

内存限制: $512\mathrm{MB}$

来源

2018 国庆雅礼 NOIP 培训。一切权利归原作者所有。侵权删除。