# HackerEarth Shil and Special Pairs problem solution

In this HackerEarth Shil and Special Pairs problem solution 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.

## HackerEarth Shil and Special Pairs problem solution.

`#include <bits/stdc++.h>using namespace std;#define ll long long int#define pb push_back#define f first#define s second#define mod 1000000007#define inf 1e8#define pi pair<ll,ll>#define pii pair<pi,ll>#define f first#define mp make_pair#define pb push_back#define s second#define rep(i,n) for(int i=0;i<n;i++)#define forup(i,a,b) for(int i=a;i<=b;i++)ll bt[100011];int N;void update(int ind){    while(ind<=N){        bt[ind]++;        ind+=(ind&-ind);    }}ll query(int ind){    ll ans=0;    while(ind>0){        ans+=bt[ind];        ind-=(ind&-ind);    }    return ans;}bool func(pii a,pii b){    return a.f.s<b.f.s;}int pos[100011];ll ans[100011];int main(){    freopen("output-10.txt","w",stdout);    freopen("input-10.txt","r",stdin);    int M,D;    cin >> N >> M >> D;    int p[N+1];    for(int i=1;i<=N;i++){        cin >> p[i];        pos[p[i]]=i;    }    vector<pii>Q;    int l,r,ind;    rep(i,M){        cin >> l >> r;        Q.push_back( mp( mp(l,r),i ) );    }    sort(Q.begin(),Q.end(),func);    int j=0;    for(int i=1;i<=N;i++){        for(int k=max(1,p[i]-D);k<=min(N,p[i]+D);k++){            if(pos[k]<=i){                update(pos[k]);            }        }        while(j<Q.size() and Q[j].f.s==i){            ans[Q[j].s]=query(Q[j].f.s)-query(Q[j].f.f-1);            j++;        }    }    rep(i,M){        cout<<ans[i]<<"\n";    }}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define mod 1000000007#define ll long long int#define pb push_back#define mk make_pair#define maxi 100002#define pp pair<pair<ll,ll>,ll>ll power(ll a, ll b) {ll x = 1, y = a;    while(b > 0) {        if(b%2 == 1) {            x=(x*y);            if(x>mod) x%=mod;        }        y = (y*y);        if(y>mod) y%=mod;        b /= 2;    }    return x;}ll tree[100002];ll read(ll idx) {    ll sum = 0;    while (idx > 0){        sum += tree[idx];        idx -= (idx & -idx);    }    return sum;}void update(ll idx ,ll val){    while (idx <= maxi) {        tree[idx] += val;        idx += (idx & -idx);    }}bool cmp(pp x, pp y){    if(x.first.second >= y.first.second) {        return false;    }    return true;}int main(){    ll n,m,d,c,i,j,k,id,p,q;    cin>>n>>m>>d;    k = 0;    ll a[n+2],idx[n+2],ans[m+2],check[n+2][2];    for(i = 1; i <= n; i++) {        cin>>a[i];        idx[a[i]] = i;        check[i][0] = min(n,a[i]+d);        check[i][1] = max(1LL,a[i]-d);    }    ll l,r;    vector<pp>dat;    for(i = 1; i <= m; i++) {        cin>>l>>r;        dat.push_back(make_pair(make_pair(l,r),i));    }    sort(dat.begin(),dat.end(),cmp);    for(i = 1; i <= n; i++) {        for(j = check[i][1]; j <= check[i][0]; j++) {            update(idx[j],idx[j] <= i);        }        for(; k < n && dat[k].first.second == i; k++) {            p = dat[k].first.first;            q = dat[k].first.second;            if(p > 1) {                ans[dat[k].second] = read(q)-read(p-1);            }            else {                ans[dat[k].second] = read(q);            }        }    }    for(i = 1; i <= m; i++) {        cout<<ans[i]<<endl;    }    return 0;}`