#P5268. [SNOI2017] 一个简单的询问

[SNOI2017] 一个简单的询问

题目描述

给你一个长度为 NN 的序列 aia_i1iN1\leq i\leq N,和 qq 组询问,每组询问读入 l1,r1,l2,r2l_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) $$

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

数据范围与原题相同,但测试数据由 LibreOJ 自制,并非原数据。

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