Problem:


Score : 800 points

Problem Statement

There are N points on a number line, i-th of which is placed on coordinate X_i.
These points are numbered in the increasing order of coordinates.
In other words, for all i (1 \leq i \leq N-1), X_i < X_{i+1} holds.
In addition to that, an integer K is given.

Process Q queries.

In the i-th query, two integers L_i and R_i are given.
Here, a set s of points is said to be a good set if it satisfies all of the following conditions.
Note that the definition of good sets varies over queries.

Each point in s is one of X_{L_i},X_{L_i+1},\ldots,X_{R_i}.

For any two distinct points in s, the distance between them is greater than or equal to K.

The size of s is maximum among all sets that satisfy the aforementioned conditions.

For each query, find the size of the union of all good sets.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq 10^9

0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9

1 \leq Q \leq 2 \times 10^5

1 \leq L_i \leq R_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
X_1 X_2 \cdots X_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

Output

For each query, print the size of the union of all good sets in a line.

Sample Input 1

5 3
1 2 4 7 8
2
1 5
1 2

Sample Output 1

4
2

In the first query, you can have at most 3 points in a good set.
There exist two good sets: \{1,4,7\} and \{1,4,8\}.
Therefore, the size of the union of all good sets is |\{1,4,7,8\}|=4.

In the second query, you can have at most 1 point in a good set.
There exist two good sets: \{1\} and \{2\}.
Therefore, the size of the union of all good sets is |\{1,2\}|=2.

Sample Input 2

15 220492538
4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194
5
6 14
1 8
1 13
7 12
4 12

Sample Output 2

4
6
11
2
3



Sample input:
5 3
1 2 4 7 8
2
1 5
1 2


Sample output:
4
2

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

INF = 10**18+3

N, K = map(int, input().split())
X = list(map(int, readline().split())) + [INF]

left = [None]*N
r = 0

for i in range(N):
    while r < N and X[r+1] - X[i] < K:
        r += 1
    left[i] = (r, i)
left = [left]
nb = N.bit_length()
for _ in range(nb):
    res = [None]*N
    for idx in range(N):
        r, i = left[-1][idx]
        if r >= N-1:
            res[idx] = (N, None)
        else:
            r1, i1 = left[-1][r+1]
            if r1 == N:
                res[idx] = (N, None)
            else:    
                res[idx] = (r1, i+i1)
    left.append(res)

right = [None]*N
l = N-1

for i in range(N-1, -1, -1):
    while 0 < l and X[i] - X[l-1] < K:
        l -= 1
    right[i] = (l, i)
right = [right]
for _ in range(nb):
    res = [None]*N
    for idx in range(N):
        l, i = right[-1][idx]
        if l <= 0:
            res[idx] = (-1, None)
        else:
            l1, i1 = right[-1][l-1]
            if l1 == -1:
                res[idx] = (-1, None)
            else:    
                res[idx] = (l1, i+i1)
    right.append(res)


Q = int(readline())
Ans = [None]*Q
for qu in range(Q):
    l, r = map(int, readline().split())
    l -= 1

    vn = l
    li = 0
    ml = 0
    for j in range(nb-1, -1, -1):
        vf, ix = left[j][vn]
        if vf < r:
            vn = vf+1
            li += ix
            ml += 1<<j
        if vn >= r:
            break
    if vn < r:
        ml += 1
        li += vn
        
    
    
    l -= 1
    r -= 1
    vn = r
    ri = 0
    mr = 0
    for j in range(nb-1, -1, -1):
        vf, ix = right[j][vn]
        if l < vf:
            vn = vf-1
            ri += ix
            mr += 1<<j
        if vn <= l:
            break
    if l < vn:
        mr += 1
        ri += vn
        
    Ans[qu] = ri-li + ml

print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = 20

@njit((i8[:],i8), cache=True)
def build_sp(X, D):
    INF = 1<<60
    N = len(X)
    X = np.append(X, INF)
    sp = np.empty((K,N+1), np.int64)
    sp_sum = np.empty((K,N+1), np.int64)
    sp[0] = np.searchsorted(X, X + D)
    sp[0,-1] = N
    sp_sum[0] = sp[0] # 移動先の座標の和
    for k in range(1, K):
        for n in range(N+1):
            to = sp[k-1,n]
            sp[k][n] = sp[k-1][to]
            sp_sum[k][n] = sp_sum[k-1,n] + sp_sum[k-1,to]
    return sp, sp_sum

@njit((i8[:,:],i8[:,:],i8,i8), cache=True)
def largest_set(sp, sp_sum, l, r):
    # 要素数と座標の和
    ret = [1,l]
    for k in range(K-1, -1, -1):
        # 2^k 進めるなら進む
        if sp[k,l] <= r:
            ret[0] += 1<<k
            ret[1] += sp_sum[k,l]
            l = sp[k,l]
    return ret

@njit((i8[:],i8,i8[:]), cache=True)
def main(X, D, LR):
    N = len(X)
    spl, spl_sum = build_sp(X, D)
    spr, spr_sum = build_sp(-X[::-1], D)
    for i in range(0, len(LR), 2):
        l, r = LR[i:i+2]
        l, r = l-1, r-1
        cl, sl = largest_set(spl, spl_sum, l,r)
        cr, sr = largest_set(spr, spr_sum, N-1-r, N-1-l)
        sr = (N-1)*cr-sr
        print(cl + sr - sl)

N, D = map(int, readline().split())
X = np.array(readline().split(), np.int64)
Q = int(readline())
LR = np.array(read().split(), np.int64)

main(X,D,LR)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

n,k = map(int,readline().split())
vs = list(map(int,readline().split()))

L=18
xid=[0]*(n*L)
xsum=[0]*(n*L)
yid=[0]*(n*L)
ysum=[0]*(n*L)

j=n
for i in reversed(range(n)):
	while i<j and vs[i]+k<=vs[j-1]:
		j-=1
	xid[i*L+0]=j
	xsum[i*L+0]=j
	for lv in range(1,L):
		a=xid[i*L+lv-1]
		if a==n:
			xid[i*L+lv]=n
		else:
			xid[i*L+lv]=xid[a*L+lv-1]
			xsum[i*L+lv]=xsum[i*L+lv-1]+xsum[a*L+lv-1]

j=-1
for i in range(n):
	while j<i and vs[j+1]+k<=vs[i]:
		j+=1
	yid[i*L+0]=j
	ysum[i*L+0]=j
	for lv in range(1,L):
		a=yid[i*L+lv-1]
		if a==-1:
			yid[i*L+lv]=-1
		else:
			yid[i*L+lv]=yid[a*L+lv-1]
			ysum[i*L+lv]=ysum[i*L+lv-1]+ysum[a*L+lv-1]

q=int(readline())
for tmp in range(q):
	l,r=map(int,readline().split())
	l-=1
	r-=1
	ans=0
	
	i=l
	ans-=i
	for lv in reversed(range(L)):
		if xid[i*L+lv]<=r:
			ans-=xsum[i*L+lv]
			i=xid[i*L+lv]
	
	i=r
	ans+=i+1
	for lv in reversed(range(L)):
		if yid[i*L+lv]>=l:
			ans+=ysum[i*L+lv]+(1<<lv)
			i=yid[i*L+lv]
	
	print(ans)