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

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

题目描述

给你一个长度为 NN 的序列 aia_i1iN1\leq i\leq N,和 qq 组询问,每组询问读入 l1,r1,l2,r2l_1,r_1,l_2,r_2,需输出

x=0get(l1,r1,x)get(l2,r2,x) \sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\cdot \text{get}(l_2,r_2,x)

get(l,r,x) \text{get}(l,r,x) 表示计算区间 [l,r][l,r] 中,数字 xx 出现了多少次。

输入格式

第一行,一个数字 NN,表示序列长度。
第二行,NN 个数字,表示 a1aNa_1\sim a_N
第三行,一个数字 QQ,表示询问个数。
4Q+34\sim Q+3 行,每行四个数字 l1,r1,l2,r2l_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%20\% 的数据,1N,Q10001\leq N,Q\leq 1000
对于另外 30%30\% 的数据,1ai501\leq a_i\leq 50
对于 100%100\% 的数据,N,Q50000N,Q\leq 500001aiN1\leq a_i\leq N1l1r1N1\leq l_1\leq r_1\leq N1l2r2N1\leq l_2\leq r_2\leq N

数据范围与原题相同,但测试数据由本站会员自制,并非原数据。
时限已按照评测机速度调整,原题时限为 2000 ms,省选评测时调整为 4000 ms,这里按 4000 ms 调整。

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