Interval Counter

Interval Counter

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个正整数序列\(\{a_i\}, i = 1,2 \cdots N\),输入\(K\)次询问,每次询问包含4个参数\(l,r,s,t\),求子区间\(\{a_l, a_{l+1} \cdots a_{r-1}, a_r\}\)中,所有位于闭区间\([s,t]\)内的值之和。

输入格式

第一行是两个正整数\(N,K\);
第二行是\(N\)个正整数\(a_1, a_2 \cdots a_N\);
之后\(K\)行依次给出每次询问,每行包含4个正整数\(l,r,s,t\),表示该次询问的参数,保证\(1 \le l \le r \le N, \quad s \le t\)。

输出格式

按照输入顺序依次输出各个询问的结果,每次输出一行。

样例

输入

7 4
1 4 3 7 6 2 5
2 5 2 5
1 6 3 7
2 3 4 8
4 7 2 5

输出

7
20
4
7

数据规模及约定

对于所有数据:\(N \le 10^5, \quad K \le 10^5, \quad 1 \le a_i \le 10^5, \quad 1 \le s \le t \le 10^5\)
其中20%的数据满足:\(N, K \le 1000\)
另外40%的数据满足:\(l \in \{1, 2\}, \quad r \in \{N - 1, N\}\)
时间限制1s,空间限制256MB。

2019.2.2补题通道

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2019-02-05 00:00
结束于
2019-02-10 00:00
持续时间
120.0 小时
主持人
参赛人数
16