#2254. 「SNOI2017」一个简单的询问

内存限制:512 MiB 时间限制:2800 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

给你一个长度为 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 出现了多少次。

输入格式

第一行,一个数字 N ,表示序列长度。
第二行, N 个数字,表示 a_1\sim a_N
第三行,一个数字 Q ,表示询问个数。
4\sim Q+3 行,每行四个数字 l_1,r_1,l_2,r_2 ,表示询问。

输出格式

对于每组询问,输出一行一个数字,表示答案。

样例

样例输入

5
1 1 1 1 1
2
1 2 3 4
1 1 4 4

样例输出

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 调整。

注意:答案有可能超过 int 的最大值。