[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)\times \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$,表示询问。
输出格式
对于每组询问,输出一行一个数字,表示答案。
输入输出样例
输入样例 #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$。
数据范围与原题相同,但测试数据由 LibreOJ 自制,并非原数据。
**注意:** 答案有可能超过 `int` 的最大值。