【PR #2】史莱姆 - Problem

给定 $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

explanation

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

样例 2

input

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}$

Public Judge

pjudge

# 21619. 【PR #2】史莱姆

输入格式

输出格式

样例 1

input

output

explanation

样例 2

input

output

样例 3

数据范围与提示