CF1185C2 Exam in BerSU (hard version)

简单版与困难版的唯一区别在于数据范围。 如果你使用 Python 编写解答，建议使用 PyPy 以加快执行速度。 Beland 州立大学新学期已经开始，许多学生正在参加考试。 Polygraph Poligrafovich 将要考察一组共有 $n$ 名学生的队伍。学生们将按照从第 $1$ 位到第 $n$ 位的顺序依次参加考试。考试规则如下： - 第 $i$ 位学生随机抽取一道题。 - 如果这道题对该学生来说太难了，他将不会作答并立即回家（这个过程非常快，可以认为不消耗时间）。该学生考试不及格。 - 如果该学生觉得题目简单，他将花费恰好 $t_i$ 分钟完成考试。之后，他会立刻获得成绩并回家。 学生们严格按照顺序、一个接一个地参加考试，中间没有任何中断。在任意时刻，Polygraph Poligrafovich 只会接收一名学生的答卷。 所有学生考试的总时长为 $M$ 分钟（保证 $\max t_i \le M$），因此排在队伍末尾的学生更有可能因时间不足而无法完成考试。 对于每一位学生 $i$，你需要计算，至少有多少名学生需要不及格（即提前离开），才能保证第 $i$ 位学生有足够的时间完成考试。 对于每一位学生 $i$，都要独立计算答案。也就是说，如果在计算第 $i_1$ 位学生的答案时需要让某位学生 $j$ 离开，那么在计算第 $i_2$ 位学生的答案时（$i_2 > i_1$），该学生 $j$ 不一定需要离开。

输入的第一行包含两个整数 $n$ 和 $M$（$1 \le n \le 2 \times 10^5$，$1 \le M \le 2 \times 10^7$），分别表示学生人数和考试总时长（分钟）。 第二行包含 $n$ 个整数 $t_i$（$1 \le t_i \le 100$），表示第 $i$ 位学生完成考试所需的时间（分钟）。 保证所有 $t_i$ 的值都不超过 $M$。

输出 $n$ 个数字，第 $i$ 个数字表示为了让第 $i$ 位学生有足够的时间完成考试，至少需要有多少名学生提前离开考试。

示例 1 的解释： 请注意，前五位学生的考试时间之和不超过 $M=15$（总和为 $1+2+3+4+5=15$）。因此，前五位学生即使所有前面的学生都参加考试，也能顺利完成考试。换句话说，前五个答案都是 $0$。 为了让第 $6$ 位学生顺利完成考试，至少需要有 $2$ 名学生提前离开（例如，第 $3$ 位和第 $4$ 位学生离开，那么第 $6$ 位学生将会在 $1+2+5+6=14$ 分钟内完成考试，不超过 $M$）。 为了让第 $7$ 位学生顺利完成考试，至少需要有 $3$ 名学生提前离开（例如，第 $2$ 位、第 $5$ 位和第 $6$ 位学生离开，那么第 $7$ 位学生将会在 $1+3+4+7=15$ 分钟内完成考试，不超过 $M$）。 由 ChatGPT 4.1 翻译