CF877F Ann and Books

在 Ann 最喜欢的书店里有 $n$ 本关于数学和经济学的书。书籍从 $1$ 到 $n$ 编号。每本书里包含非负数量的题目。 今天有促销：可以以固定价格购买从 $l$ 到 $r$ 的某个区间中的任意子区间。 Ann 决定她想购买一个非空子区间，使得该区间内数学题目的数量恰好比经济学题目的数量多 $k$。注意，$k$ 可能为正、负或零。 可惜 Ann 不确定促销在哪个区间，但她有 $q$ 个假设区间。对于每个假设，她都想知道满足条件的子区间数量（她花在选择上的时间取决于这个数量）。 现在 Ann 正忙于解决其他问题，她请求你帮忙。对于她的每个假设，计算在给定区间内使得数学题目数量比经济学题目数量恰好多 $k$ 的子区间数量。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100000$，$-10^9 \leq k \leq 10^9$），分别表示书的数量以及所需的题目数量差值。 第二行包含 $n$ 个整数 $t_1,t_2,\ldots,t_n$（$1 \leq t_i \leq 2$），其中 $t_i$ 为 $1$ 表示第 $i$ 本书是数学书，$2$ 表示经济学书。 第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 为第 $i$ 本书中的题目数量。 第四行包含一个整数 $q$（$1 \leq q \leq 100000$），表示假设的数量。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），描述第 $i$ 个 Ann 的假设区间。

输出 $q$ 行，第 $i$ 行输出第 $i$ 个假设区间内满足条件的子区间数量。

在第一个样例中，Ann 可以购买的子区间有 $[1;1],[2;2],[3;3],[2;4]$，因为这些子区间中数学题目的数量恰好比经济学题目的数量多 $1$。所以对于每个假设，我们要统计这些子区间有多少是该区间的子区间。 区间 $[1;1]$ 和 $[2;2]$ 是 $[1;2]$ 的子区间。 区间 $[1;1],[2;2],[3;3]$ 是 $[1;3]$ 的子区间。 区间 $[1;1],[2;2],[3;3],[2;4]$ 是 $[1;4]$ 的子区间。 区间 $[3;3]$ 是 $[3;4]$ 的子区间。 由 ChatGPT 5 翻译