# HackerRank Almost Equal - Advanced problem solution

In this HackerRank Almost Equal - Advanced problem solution, we have 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?.

## Problem solution in 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();
}
}```

## Problem solution in 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<sz) up++;
ret += up-(i+1);
}
return ret;
}
inline ll intwov(int* v1, int sz1, int* v2, int sz2)
{
if(sz1<=0 or sz2<=0) return 0;

ll ret=0; int low=0, up=0;
rep(i, 0, sz1-1)
{
while(v2[low] < v1[i]-k and low<sz2) low++;
while(v2[up] <= v1[i]+k and up<sz2) up++;
ret += up-low;
}
return ret;
}

void process()
{
for(int i=0; i*sqr<n; ++i)
{
int s=i*sqr, e=min(n-1, s+sqr-1);
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<szb[j]) low++;
while(buck[j][up].first <= buck[i+1][l].first+k and up<szb[j]) up++;
b1d[buck[i+1][l].second][j] += up-low; val += up-low;
}
b2d[j][i+1]+=val;
}
}

for(int i=0; i*sqr<=n; ++i)
{
for(int j=i+2; szb[j]; ++j)
{
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<szb[j]) low++;
while(buck[j][up].first <= buck[i+1][l].first+k and up<szb[j]) up++;
b1d[buck[i+1][l].second][j] += up-low;
}
}
}
}

int main()
{
//rf; wf;
scan(n); scan(k); sqr=sqrt(n);
rep(i, 0, n-1)
scan(h[i]);

process();
cum1d();
cum2d();

scanf("%d", &q);
while(q--)
{
int l, r;
scan(l); scan(r);
ll ans=0;

int sqrl=l/sqr, sqrr=r/sqr, szl=0, szr=0; sqrl++;

rep(i, 0, szb[sqrl]-1)
if(buck[sqrl][i].second>=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;
}```

## Problem solution in 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;
}
```