H. Query Difference
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers and a fixed integer $$$k$$$. Process $$$q$$$ queries of two types:

1. A count query, where you are given $$$l$$$ and $$$r$$$ and count the number of pairs $$$(i, j)$$$ such that $$$l \leq i \lt j \leq r$$$ and $$$a_j - a_i = k$$$.

2. An update query, where you are given $$$p$$$ and $$$x$$$ and set $$$a_p = x$$$.

Input

The first line contains three integers $$$n$$$, $$$q$$$, and $$$k$$$ $$$(1 \leq n, q, k \leq 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^5)$$$.

Each of the next $$$q$$$ lines is one of:

  • 1 l r: count query $$$(1 \leq l \lt r \leq n)$$$
  • 2 p x: update query $$$(1 \leq p \leq n, 1 \leq x \leq 10^5)$$$
Output

For each count query, output the number of pairs $$$(i, j)$$$ such that $$$l \leq i \lt j \leq r$$$ and $$$a_j - a_i = k$$$.

Scoring
SubtaskConstraintPoints
$$$1$$$$$$n, q \leq 1000$$$$$$40$$$
$$$2$$$There are no update queries$$$60$$$
$$$3$$$No additional constraints$$$100$$$
Example
Input
6 5 3
1 4 7 4 1 4
1 1 6
1 2 5
2 4 7
1 1 4
1 1 6
Output
5
1
3
5
Note

For the first query, $$$(i, j) = (1, 2), (1, 4), (1, 6), (2, 3), (5, 6)$$$ satisfy the constraints.

For the second query, only $$$(i, j) = (2, 3)$$$ satisfies the constraints.

After the third query, the array is modified to $$$[1, 4, 7, 7, 1, 4]$$$.