题目描述
给你一个长度为 N 的序列 ai,1≤i≤N,和 q 组询问,每组询问读入 l1,r1,l2,r2,需输出
x=0∑∞get(l1,r1,x)⋅get(l2,r2,x)get(l,r,x) 表示计算区间 [l,r] 中,数字 x 出现了多少次。
输入格式
第一行,一个数字 N,表示序列长度。
第二行,N 个数字,表示 a1∼aN。
第三行,一个数字 Q,表示询问个数。
第 4∼Q+3 行,每行四个数字 l1,r1,l2,r2,表示询问。
输出格式
对于每组询问,输出一行一个数字,表示答案。
数据范围与提示
对于 20% 的数据,1≤N,Q≤1000;
对于另外 30% 的数据,1≤ai≤50;
对于 100% 的数据,N,Q≤50000,1≤ai≤N,1≤l1≤r1≤N,1≤l2≤r2≤N。
数据范围与原题相同,但测试数据由本站会员自制,并非原数据。
时限已按照评测机速度调整,原题时限为 2000 ms,省选评测时调整为 4000 ms,这里按 4000 ms 调整。
注意:答案有可能超过 int
的最大值。