Algorithm

Problem Name: Data Structures - Almost Equal - Advanced

In this HackerRank in Data Structures - Almost Equal - Advanced solutions,

A Sumo wrestling championship is scheduled to be held this winter in the HackerCity where N wrestlers from different parts of the world are going to participate. The rules state that two wrestlers can fight against each other if and only if the difference in their height is less than or equal to K,
(i.e) wrestler A and wrestler B can fight if and only if |height(A)-height(B)|<=K.

Given an array H[], where H[i] represents the height of the ith fighter, for a given l, r where `0 <= l <= r < N`, can you count the number of pairs of fighters between l and r (both inclusive) who qualify to play a game?

Input Format
The first line contains an integer N and K separated by a single space representing the number of Sumo wrestlers who are going to participate and the height difference K.
The second line contains N integers separated by a single space, representing their heights H[0] H[1] ... H[N - 1].
The third line contains Q, the number of queries. This is followed by Q lines each having two integers l and r separated by a space.

Output Format
For each query Q, output the corresponding value of the number of pairs of fighters for whom the absolute difference of height is not greater that K.

Constraints
1 <= N <= 100000
0 <= K <= 109
0 <= H[i] <= 109
1 <= Q <= 100000
0 <= l <= r < N

Sample Input

```5 2
1 3 4 3 0
3
0 1
1 3
0 4
```

Sample Output

```1
3
6
```

Explanation
Query #0: Between 0 and 1 we have i,j as (0,1) and |H[0]-H[1]|=2 therefore output is 1.
Query #1: The pairs (H[1],H[2]) (H[1],H[3]) and (H[2],H[3]) are the pairs such that |H[i]-H[j]| <=2. Hence output is 3.
Query #2: Apart from those in Query #1, we have (H[0],H[1]), (H[0], H[3]), (H[0], H[4]), hence 6.

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void QQ(int x,int y);
void removee(int X);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
void update(int idx,int val,int MaxVal);
int H[300000],rH[300000],q[2][100000],qq[2][100000],idx[300000],tree[300001],NN,cl,cr;
long long ans[100000],x;

int main(){
int K,Q,i,j;
scanf("%d%d",&NN,&K);
for(i = 0; i  <  NN; i++){
scanf("%d",&H[3*i]);
H[3*i+1] = H[3*i]-K;
H[3*i+2] = H[3*i]+K;
idx[3*i] = 3*i;
idx[3*i+1] = 3*i+1;
idx[3*i+2] = 3*i+2;
}
sort_a2(H,idx,3*NN);
for(i = j = 0; i  <  3*NN; i++){
if(i && H[i] != H[i-1])
j++;
rH[idx[i]] = j;
}
scanf("%d",&Q);
for(i = 0; i < Q; i++){
scanf("%d%d",&q[0][i],&q[1][i]);
q[1][i]++;
}
for(i = 0, j = (int)sqrt(NN); i  <  Q; i++){
qq[0][i] = q[0][i]/j;
qq[1][i] = q[1][i];
idx[i] = i;
}
sort_a3(&qq[0][0],&qq[1][0],idx,Q);
for(i = cl = cr = 0, x= 0; i  <  Q; i++){
QQ(q[0][idx[i]],q[1][idx[i]]);
ans[idx[i]]=x;
}
for(i = 0; i  <  Q; i++)
printf("%lld\n",ans[i]);
return 0;
}
void QQ(int x,int y){
while(cl < x)
removee(cl++>;
while(cl>x)
while(cr < y)
while(cr>y)
removee(--cr);
return;
}
if(rH[3*X+1])
x+=y;
update(rH[3*X]+1,1,3*NN);
return;
}
void removee(int X){
if(rH[3*X+1])
x-=y-1;
update(rH[3*X]+1,-1,3*NN);
return;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a = (int*)malloc(m*sizeof(int));
right_a = (int*)malloc((size-m)*sizeof(int));
left_b = (int*)malloc(m*sizeof(int));
right_b = (int*)malloc((size-m)*sizeof(int));
for(i = 0; i  <  m; i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i = 0; i  <  size-m; i++){
right_a[i] = a[i+m];
right_b[i] = b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size){
int i = 0, j = 0;
while (i  <  left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i]  < = right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
void sort_a3(int*a,int*b,int*c,int size){
if (size  <  2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a = (int*)malloc(m*sizeof(int));
right_a = (int*)malloc((size-m)*sizeof(int));
left_b = (int*)malloc(m*sizeof(int));
right_b = (int*)malloc((size-m)*sizeof(int));
left_c = (int*)malloc(m*sizeof(int));
right_c = (int*)malloc((size-m)*sizeof(int));
for(i = 0; i  <  m; i++){
left_a[i] = a[i];
left_b[i] = b[i];
left_c[i] = c[i];
}
for(i = 0; i  <  size-m; i++){
right_a[i] = a[i+m];
right_b[i] = b[i+m];
right_c[i] = c[i+m];
}
sort_a3(left_a,left_b,left_c,m);
sort_a3(right_a,right_b,right_c,size-m);
merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
int i = 0, j = 0;
while (i  <  left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] == right_a[j]) {
if(left_b[i] < =right_b[j]){
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
}
else{
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
} else if (left_a[i]  <  right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
int sum = 0;
while(idx>0){
sum+=tree[idx];
idx-=(idx&-idx);
}
return sum;
}
void update(int idx,int val,int MaxVal){
while(idx < =MaxVal){
tree[idx]+=val;
idx+=(idx&-idx);
}
return;
}
``````
Copy The Code &

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
#define rep(i, s, n) for(int i=int(s); i < =int(n); ++i)
#define rf freopen("in.in", "r", stdin)
#define wf freopen("out.out", "w", stdout)
using namespace std;
#define mp make_pair
#define ll long long
const int mx=1e5+10;

#define gc getchar_unlocked
void scan(int &x)
{
register int c = gc();
x = 0;
for(;(c < 48 || c>57);c = gc());
for(;c>47 && c < 58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}

static ll b2d[410][410], b1d[mx][410];
static int h[mx], szb[410], lb[410], rb[410];
pair < int, int> bb[410], *buck[410];
int n, k, q, sqr;

inline void cum2d()
{
rep(i, 1, 409) rep(j, 1, 409)
b2d[i][j] += b2d[i-1][j]+b2d[i][j-1]-b2d[i-1][j-1];
}
inline void cum1d()
{
rep(i, 0, n) rep(j, 1, 409)
b1d[i][j] += b1d[i][j-1];
}

inline ll inonev(int* v, int sz)
{
if(sz <= 0) return 0;

ll ret = 0; int up=0;
rep(i, 0, sz-1)
{
while(v[up]  < = v[i]+k and up;
buck[i+1]=new pair < int, int>[e-s+1]; szb[i+1]=e-s+1;

rep(j, s, e)
buck[i+1][j-s] = mp(h[j], j),
lb[j-s] = h[j];
sort(lb, lb+szb[i+1]);
sort(buck[i+1], buck[i+1]+szb[i+1]);

ll val=inonev(lb, szb[i+1]);
b2d[i+1][i+1] += val;

rep(j, 1, i)
{
val=0; int up=0, low=0;
rep(l, 0, szb[i+1]-1)
{
while(buck[j][low].first  <  buck[i+1][l].first-k and low=l and buck[sqrl][i].second<=r)
lb[szl++]=buck[sqrl][i].first;
rep(i, 0, szb[sqrr+1]-1>
if(buck[sqrr+1][i].second>=l and buck[sqrr+1][i].second<=r)
rb[szr++]=buck[sqrr+1][i].first;

ans+=inonev(lb, szl);
if(sqrr+1==sqrl) {printf("%lld\n", ans); continue;}
ans+=inonev(rb, szr);

ans += intwov(lb, szl, rb, szr);
ans += b2d[sqrr][sqrr]-b2d[sqrr][sqrl]-b2d[sqrl][sqrr]+b2d[sqrl][sqrl];

rep(i, l, sqr*sqrl-1)
ans += b1d[i][sqrr]-b1d[i][sqrl];
rep(i, sqr*sqrr, r)
ans += b1d[i][sqrr]-b1d[i][sqrl];

printf("%lld\n", ans>;
}
return 0;
}
``````
Copy The Code &

#3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.util.*;

public class Solution {

static int nn;
static int block;
static int[] fenwick;
static long cnt = 0;

static class B implements Comparable < B> {
int l;
int r;
int id;

@Override
public int compareTo(B o) {
int i = l/block;
int j = o.l/block;
if (i != j) {
return i - j;
}
if (r != o.r) {
return r - o.r;
}
return l - o.l;
}
}

static int getSum(int x) {
int s = 0;
for (; x != 0; x &= x-1)
s += fenwick[x-1];
return s;
}

static class Node {
int l;
int r;
int h;

public Node(int l, int r, int h) {
this.l = l;
this.r = r;
this.h = h;
}

void remove() {
cnt -= getSum(r) - getSum(l);
}

cnt += getSum(r) - getSum(l);
}

void add(int x, int v) {
for (; x  <  nn; x |= x+1)
fenwick[x] += v;
}
}

static public int lowerBound(int[] arr, int len, int key) {
if (key  < = arr[0]) {
return 0;
}
if (key > arr[len - 1]) {
return 0;
}

int index = Arrays.binarySearch(arr, 0, len, key);
if (index  <  0) {
index = - index - 1;
if (index < 0) {
return 0;
}
}
return index;
}

static public int upperBound(int[] arr, int len, int key) {
int index = Arrays.binarySearch(arr, 0, len, key+1);
if (index  <  0) {
index = - index - 1;
if (index < 0 || index > len) {
return 0;
}
}
return index;
}

public static int unique(int[] arr) {
if (arr.length == 1) return 1;
int len = 1;
while (len  <  arr.length && arr[len] != arr[len-1]) {
len++;
}
for (int i = len + 1; i  <  arr.length; i++) {
if (arr[i] != arr[len - 1]) {
len++;
arr[len - 1] = arr[i];
}
}
return len;
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());

int[] a = new int[n];
int[] c = new int[n];
for (int i = 0; i  <  n; i++) {
int item = Integer.parseInt(st.nextToken());
c[i] = a[i] = item;
}
Arrays.sort(c);
nn = unique(c);

Node[] nodes = new Node[n];
for (int i = 0; i  <  n; i++) {
int l = lowerBound(c, nn, a[i]-k);
int r = upperBound(c, nn, a[i]+k);
int h = lowerBound(c, nn, a[i]);
nodes[i] = new Node(l, r, h);
}

int q = Integer.parseInt(st.nextToken());

B[] b = new B[q];
block = (int) Math.max(1.0, Math.sqrt((double)(n)*n/Math.max(1, q)));
for (int i = 0; i  <  q; i++) {
b[i] = new B();
b[i].id = i;
b[i].l = Integer.parseInt(st.nextToken());
b[i].r = Integer.parseInt(st.nextToken()) + 1;
}
Arrays.sort(b);
int l = 0;
int r = 0;
fenwick = new int[n];
long[] result = new long[q];
for (int i = 0; i  <  q; i++) {
while (l < b[i].l) {
nodes[l++].remove();
}
while (b[i].l  <  l) {
}
while (b[i].r < r) {
nodes[--r].remove();
}
while (r  <  b[i].r) {
}
result[b[i].id] = cnt;
}

for (int i = 0; i  <  result.length; i++) {
bw.write(String.valueOf(result[i]));

if (i != result.length - 1) {
bw.write("\n");
}
}

bw.newLine();

bw.close();
br.close();
}
}
``````
Copy The Code &