Public Judge

pjudge

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

#21619. 【PR #2】史莱姆

Statistiques

一个时限调大的版本:https://qoj.ac/problem/3576


给定 $n$ 只史莱姆排成一列,第 $i$ 只史莱姆的大小为 $a_i$。

对于一些史莱姆,可以进行一局游戏:给定非负整数 $k$,设第 $i$ 只史莱姆可以吃掉第 $j$ 只史莱姆当且仅当 $a_i-a_j\ge k$,此时第 $j$ 只史莱姆被删除而 $a_i$ 变为 $a_i+a_j$;史莱姆之间可以任意互相吃,若没有史莱姆能吃掉其他史莱姆则游戏结束;若最后仅剩下一只史莱姆则这只史莱姆获胜,否则没有史莱姆获胜。

$q$ 次询问 $l,r,k$,求在 $[l,r]$ 这段区间的史莱姆进行游戏的情况下,有多少只史莱姆可能获胜。

注意每组询问之间是独立的,即在询问过程中不会有史莱姆吃掉其他史莱姆。

输入格式

第一行,两个正整数 $n,q$。

第二行,$n$ 个正整数 $a_1,\cdots,a_n$。

之后 $q$ 行,每行两个正整数 $l,r$ 和非负整数 $k$,表示一组询问。

输出格式

共 $q$ 行,每行一个非负整数,表示一组询问的答案。

样例 1

input

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

output

5
1
1
0

explanation

例如对于第 $2$ 组询问:$k=4$,大小分别为 $3,7,5$ 的史莱姆进行游戏,则大小为 $7$ 的史莱姆可以先吃掉大小为 $3$ 的史莱姆,此时其大小变为 $10$,然后吃掉大小为 $5$ 的史莱姆从而获胜;可以证明大小为 $3$ 和 $5$ 的史莱姆无法获胜。

样例 2

input

3 2
3 3 3
1 3 1
1 3 0

output

0
3

样例 3

见下发文件,该样例符合子任务 $6$ 的限制。

数据范围与提示

对于所有数据,$2\le n\le 2\cdot 10^5$,$1\le q\le 2\cdot 10^5$,$1\le a_i\le 10^9$,$1\le l\le r\le n$,$0\le k\le 10^9$。

子任务编号 特殊限制 分值
$1$ $n,q\le 500$ $7$
$2$ $n,q\le 3000$ $15$
$3$ $a_i$ 单调不降 $24$
$4$ $n,q\le 5\cdot 10^4$,$a_i\le 10^6$ $20$
$5$ $n,q\le 10^5$ $19$
$6$ $ $ $15$

时间限制:$\texttt{3s}$

空间限制:$\texttt{512MB}$