English · Original
Chinese · Translation
Formal · Original
In Ann's favorite book shop are as many as _n_ books on math and economics. Books are numbered from 1 to _n_. Each of them contains non-negative number of problems.
Today there is a sale: any subsegment of a segment from _l_ to _r_ can be bought at a fixed price.
Ann decided that she wants to buy such non-empty subsegment that the sale operates on it and the number of math problems is greater than the number of economics problems **exactly** by _k_. Note that _k_ may be positive, negative or zero.
Unfortunately, Ann is not sure on which segment the sale operates, but she has _q_ assumptions. For each of them she wants to know the number of options to buy a subsegment satisfying the condition (because the time she spends on choosing depends on that).
Currently Ann is too busy solving other problems, she asks you for help. For each her assumption determine the number of subsegments of the given segment such that the number of math problems is greaten than the number of economics problems on that subsegment exactly by _k_.
## Input
The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 100 000, - 109 ≤ _k_ ≤ 109) — the number of books and the needed difference between the number of math problems and the number of economics problems.
The second line contains _n_ integers _t_1, _t_2, ..., _t__n_ (1 ≤ _t__i_ ≤ 2), where _t__i_ is 1 if the _i_\-th book is on math or 2 if the _i_\-th is on economics.
The third line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 109), where _a__i_ is the number of problems in the _i_\-th book.
The fourth line contains a single integer _q_ (1 ≤ _q_ ≤ 100 000) — the number of assumptions.
Each of the next _q_ lines contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ _n_) describing the _i_\-th Ann's assumption.
## Output
Print _q_ lines, in the _i_\-th of them print the number of subsegments for the _i_\-th Ann's assumption.
[samples]
## Note
In the first sample Ann can buy subsegments \[1;1\], \[2;2\], \[3;3\], \[2;4\] if they fall into the sales segment, because the number of math problems is greater by 1 on them that the number of economics problems. So we should count for each assumption the number of these subsegments that are subsegments of the given segment.
Segments \[1;1\] and \[2;2\] are subsegments of \[1;2\].
Segments \[1;1\], \[2;2\] and \[3;3\] are subsegments of \[1;3\].
Segments \[1;1\], \[2;2\], \[3;3\], \[2;4\] are subsegments of \[1;4\].
Segment \[3;3\] is subsegment of \[3;4\].
在 Ann 最喜欢的书店里，有 #cf_span[n] 本关于数学和经济学的书。这些书的编号从 #cf_span[1] 到 #cf_span[n]，每本书包含非负数量的问题。
今天正在进行促销：任何位于区间 #cf_span[l] 到 #cf_span[r] 内的子段都可以以固定价格购买。
Ann 决定购买一个非空子段，使得促销活动适用于该子段，并且数学问题的数量比经济学问题的数量恰好多 #cf_span[k] 个。注意，#cf_span[k] 可能为正数、负数或零。
不幸的是，Ann 不确定促销活动具体适用于哪个区间，但她有 #cf_span[q] 种假设。对于每种假设，她希望知道满足条件的子段选择方案数量（因为她花费在选择上的时间取决于这个数量）。
目前 Ann 忙于解决其他问题，她向你寻求帮助。对于她的每个假设，请确定在给定区间内有多少个子段，使得该子段上数学问题的数量比经济学问题的数量恰好多 #cf_span[k] 个。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[ - 109 ≤ k ≤ 109]），分别表示书的数量和所需的数学问题与经济学问题数量之差。
第二行包含 #cf_span[n] 个整数 #cf_span[t1, t2, ..., tn]（#cf_span[1 ≤ ti ≤ 2]），其中 #cf_span[ti] 为 #cf_span[1] 表示第 #cf_span[i] 本书是数学书，为 #cf_span[2] 表示是经济学书。
第三行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示第 #cf_span[i] 本书中的问题数量。
第四行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 100 000]），表示假设的数量。
接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]），描述 Ann 的第 #cf_span[i] 个假设。
请输出 #cf_span[q] 行，第 #cf_span[i] 行输出第 #cf_span[i] 个假设对应的满足条件的子段数量。
在第一个样例中，如果这些子段落在促销区间内，Ann 可以购买子段 #cf_span[[1;1], [2;2], [3;3], [2;4]]，因为在这些子段上数学问题的数量比经济学问题的数量多 #cf_span[1] 个。因此，对于每个假设，我们需要计算有多少个这样的子段是给定区间的子段。
子段 #cf_span[[1;1]] 和 #cf_span[[2;2]] 是 #cf_span[[1;2]] 的子段。
子段 #cf_span[[1;1], [2;2]] 和 #cf_span[[3;3]] 是 #cf_span[[1;3]] 的子段。
子段 #cf_span[[1;1], [2;2], [3;3], [2;4]] 是 #cf_span[[1;4]] 的子段。
子段 #cf_span[[3;3]] 是 #cf_span[[3;4]] 的子段。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[ - 109 ≤ k ≤ 109]），分别表示书的数量和所需的数学问题与经济学问题数量之差。第二行包含 #cf_span[n] 个整数 #cf_span[t1, t2, ..., tn]（#cf_span[1 ≤ ti ≤ 2]），其中 #cf_span[ti] 为 #cf_span[1] 表示第 #cf_span[i] 本书是数学书，为 #cf_span[2] 表示是经济学书。第三行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示第 #cf_span[i] 本书中的问题数量。第四行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 100 000]），表示假设的数量。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]），描述 Ann 的第 #cf_span[i] 个假设。
## Output
请输出 #cf_span[q] 行，第 #cf_span[i] 行输出第 #cf_span[i] 个假设对应的满足条件的子段数量。
[samples]
## Note
在第一个样例中，如果这些子段落在促销区间内，Ann 可以购买子段 #cf_span[[1;1], [2;2], [3;3], [2;4]]，因为在这些子段上数学问题的数量比经济学问题的数量多 #cf_span[1] 个。因此，对于每个假设，我们需要计算有多少个这样的子段是给定区间的子段。子段 #cf_span[[1;1]] 和 #cf_span[[2;2]] 是 #cf_span[[1;2]] 的子段。子段 #cf_span[[1;1], [2;2]] 和 #cf_span[[3;3]] 是 #cf_span[[1;3]] 的子段。子段 #cf_span[[1;1], [2;2], [3;3], [2;4]] 是 #cf_span[[1;4]] 的子段。子段 #cf_span[[3;3]] 是 #cf_span[[3;4]] 的子段。
**Definitions**
Let $ n, k \in \mathbb{Z} $, with $ 1 \leq n \leq 10^5 $, $ -10^9 \leq k \leq 10^9 $.
Let $ t = (t_1, \dots, t_n) \in \{1,2\}^n $, where $ t_i = 1 $ if book $ i $ is math, $ t_i = 2 $ if economics.
Let $ a = (a_1, \dots, a_n) \in \mathbb{Z}_{\geq 0}^n $, where $ a_i $ is the number of problems in book $ i $.
Define the **net difference** for book $ i $:
$$
d_i =
\begin{cases}
a_i & \text{if } t_i = 1 \\
-a_i & \text{if } t_i = 2
\end{cases}
$$
Let $ s_0 = 0 $, and for $ j \in \{1, \dots, n\} $, define the prefix sum:
$$
s_j = \sum_{i=1}^j d_i
$$
For a subsegment $ [l, r] $, the net difference is $ s_r - s_{l-1} $.
Let $ q \in \mathbb{Z} $, $ 1 \leq q \leq 10^5 $, be the number of queries.
Each query is a segment $ [L_i, R_i] $, $ 1 \leq L_i \leq R_i \leq n $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ -10^9 \leq k \leq 10^9 $
3. $ 1 \leq t_i \leq 2 $, $ 0 \leq a_i \leq 10^9 $
4. $ 1 \leq q \leq 10^5 $
5. $ 1 \leq L_i \leq R_i \leq n $ for all $ i \in \{1, \dots, q\} $
**Objective**
For each query $ i \in \{1, \dots, q\} $, compute the number of pairs $ (l, r) $ such that:
- $ L_i \leq l \leq r \leq R_i $,
- $ s_r - s_{l-1} = k $.
Equivalently, for fixed $ [L_i, R_i] $, count:
$$
\left| \left\{ (l, r) \in \mathbb{Z}^2 \mid L_i \leq l \leq r \leq R_i \text{ and } s_r - s_{l-1} = k \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "F. Ann and Books",
"description": {
"content": "In Ann's favorite book shop are as many as _n_ books on math and economics. Books are numbered from 1 to _n_. Each of them contains non-negative number of problems. Today there is a sale: any subsegm",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF877F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "In Ann's favorite book shop are as many as _n_ books on math and economics. Books are numbered from 1 to _n_. Each of them contains non-negative number of problems.\n\nToday there is a sale: any subsegm...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在 Ann 最喜欢的书店里，有 #cf_span[n] 本关于数学和经济学的书。这些书的编号从 #cf_span[1] 到 #cf_span[n]，每本书包含非负数量的问题。\n\n今天正在进行促销：任何位于区间 #cf_span[l] 到 #cf_span[r] 内的子段都可以以固定价格购买。\n\nAnn 决定购买一个非空子段，使得促销活动适用于该子段，并且数学问题的数量比经济学问题的数量恰好多 #c...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z} $, with $ 1 \\leq n \\leq 10^5 $, $ -10^9 \\leq k \\leq 10^9 $. \nLet $ t = (t_1, \\dots, t_n) \\in \\{1,2\\}^n $, where $ t_i = 1 $ if book $ i $ is math, $ t_i = ...",
"is_translate": false,
"language": "Formal"
}
]
}