shil-and-special-pairs

Shil has a permutation p1 , p2 .. pN of numbers from 1 to N and M queries. Each query consists of two integers l and  r . Answer to each query is total number of pairs[i , j] such that l ≤ i ≤ j ≤ r and|pi - pj| ≤ D. 

INPUT:
First line consists of three integers N, M and D. Next line consists of permutation p1 , p2 .. pN of the first N natural numbers. Next M lines consists of two integers l and r . 

OUTPUT:
Output M integers with i^th integer corresponding answer to i^th query.

CONSTRAINTS:
1 ≤ N, M ≤ 10^5
1 ≤ D ≤ 10
1 ≤ pi ≤ N 
1 ≤ l ≤ r ≤ N

SAMPLE INPUT
5 5 1
1 4 2 3 5
1 3
2 4
1 5
2 2
4 5

SAMPLE OUTPUT
4
5
9
1
2

Explanation

For 1^st query , all the pairs are (1,1) , (4,4) , (2,2) , (1,2).
For 2^nd query , all the pairs are (4,4) , (2,2) , (3,3) , (4,3) , (2,3).
For 3^rd query , all the pairs are (1,1) , (4,4) , (2,2) , (3,3) , (5,5) , (1,2) , (4,5) , (4,3) , (2,3).
Note that numbers in the bracket are values not indices of permutation.

Source: hackerearth | Difficulty: HARD
Tags: Bit manipulation

Sorting

Data structures


Solutions:
(n, m, d) = [int(v) for v in input().strip().split(' ')]
arr = [int(v) for v in input().strip().split(' ')]
pos = [0] * (n + 1)
q = []

for i in range(0, len(arr)):
	pos[arr[i]] = i

for i in range(0, m):
	(l, r) = [int(v) for v in input().strip().split(' ')]
	q.append(((l, r), i))
q = sorted(q, key=lambda tp: tp[0][1])

tree = [0] * (n + 1)


def update(pos):
	while pos <= n:
		tree[pos] += 1
		pos += pos & (-pos)


def query(pos):
	ans = 0
	while pos > 0:
		ans += tree[pos]
		pos -= pos & (-pos)
	return ans

j = 0
ans = [0] * (m + 1)
for i in range(1, n + 1):
	for v in range(max(1, arr[i - 1] - d), min(n + 1, arr[i - 1] + d + 1)):
		if pos[v] + 1 <= i:
			update(pos[v] + 1)
	while j < len(q) and q[j][0][1] == i:
		ans[q[j][1]] = query(q[j][0][1]) - query(q[j][0][0] - 1)
		j += 1
for i in range(m):
	print(ans[i])