A6812. 「SNOI2017」一个简单的询问
编程题
提高+/省选-
知识点
题目描述
给你一个长度为 $N$ 的序列 $a_i$，$1\leq i\leq N$，和 $q$ 组询问，每组询问读入 $l_1,r_1,l_2,r_2$，需输出
$$ \sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\cdot \text{get}(l_2,r_2,x) $$
$ \text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中，数字 $x$ 出现了多少次。
$$ \sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\cdot \text{get}(l_2,r_2,x) $$
$ \text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中，数字 $x$ 出现了多少次。
输入格式
第一行，一个数字 $N$，表示序列长度。
第二行，$N$ 个数字，表示 $a_1\sim a_N$。
第三行，一个数字 $Q$，表示询问个数。
第 $4\sim Q+3$ 行，每行四个数字 $l_1,r_1,l_2,r_2$，表示询问。
第二行，$N$ 个数字，表示 $a_1\sim a_N$。
第三行，一个数字 $Q$，表示询问个数。
第 $4\sim Q+3$ 行，每行四个数字 $l_1,r_1,l_2,r_2$，表示询问。
输出格式
对于每组询问，输出一行一个数字，表示答案。
输入输出样例
输入 #1
5 1 1 1 1 1 2 1 2 3 4 1 1 4 4
输出 #1
4 1
说明/提示
对于 $20\%$ 的数据，$1\leq N,Q\leq 1000$；
对于另外 $30\%$ 的数据，$1\leq a_i\leq 50$；
对于 $100\%$ 的数据，$N,Q\leq 50000$，$1\leq a_i\leq N$，$1\leq l_1\leq r_1\leq N$，$1\leq l_2\leq r_2\leq N$。
数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000 ms，省选评测时调整为 4000 ms，这里按 4000 ms 调整。
**注意**：答案有可能超过
对于另外 $30\%$ 的数据，$1\leq a_i\leq 50$；
对于 $100\%$ 的数据，$N,Q\leq 50000$，$1\leq a_i\leq N$，$1\leq l_1\leq r_1\leq N$，$1\leq l_2\leq r_2\leq N$。
数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000 ms，省选评测时调整为 4000 ms，这里按 4000 ms 调整。
**注意**：答案有可能超过
int 的最大值。