4296. [TIOJ - 114學年度複試] Interactive

【题目背景】

pooh 很想买 Ina 的五周年纪念商品，因此他决定要去打工。 他的打工是要去帮忙一个活动分组，该活动会有 $N$ 个人参加，这 $N$ 个人排成一排。因为该活动需要有互动性，因此主办方预先帮 pooh 收集了每个参加的人的互动度。

【题目描述】

已知由左至右第 $i$ 个人的互动度为 $a_i$。定义一个组别是 $a$ 上的一个区间 $[l, r]$。对于一个组别 $[l, r]$，如果它存在一个子区间，其互动度总和大于等于互动参数 $k$，我们就定义该组别是有互动性的 (Interactive)。

注意到空区间也是一个子区间（和为 0），因此若互动参数 $k \le 0$，所有组别都是有互动性的组别。

现在主办方有 $Q$ 个问题想问 pooh，每个问题有一个参数 $x_i$。主办方好奇：如果这个活动的组别要求每一组不超过 $x_i$ 人，那么有几个有互动性的组别是符合要求的呢？pooh 因此求助于你，希望你可以帮他回答这些问题。

【输入格式】

第一行包含两个整数 $N, k$，代表会有几个人参加活动，与该活动的互动参数。
第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，代表由左至右 $N$ 个人的互动度。
第三行包含一个整数 $Q$，代表主办方想问 pooh 几个问题。
接下来 $Q$ 行，每行有一个整数，第 $i+3$ 行为 $x_i$，代表每笔询问要求组别不超过的人数。

【输出格式】

输出 $Q$ 行，第 $i$ 行代表有几组大小不超过 $x_i$ 的组别是有互动性的。

【样例输入】

8 4
2 5 1 -2 3 -1 2 1
3
1
3
4

【样例输出】

1
6
10

【样例说明】

对于样例测资 1，所有不超过 4 人的有互动性组别为：
$[1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [2, 5], [4, 7], [5, 7], [5, 8]$。
注意到虽然 $[4, 7]$ 的互动度总和为 2，但它的子区间 $[5, 7]$ 互动度总和为 4，满足条件，故它是一个有互动性的组别。

【数据规模与约定】

• $1 \le N, Q \le 2 \times 10^5$
• $0 \le k \le 2 \times 10^{14}$
• $-10^9 \le a_i \le 10^9$
• $1 \le x_i \le N$
• 大洋里（仅提供子任务 $5$ 的样例一个）
  

【来源】

114 学年度台湾省建国中学信息学科能力竞赛：复试