一个长度为N的正整数数组A，给出一个数K以及Q个查询，每个查询包含2个数l和r，对于每个查询输出从A[i]到A[j]中，有多少对数，abs(A[i] - A[j]) <= K(abs表示绝对值)。

Input

第1行：3个数N，K，Q，中间用空格分隔，N为数组A的长度，K为差距，Q为查询的数量。(2 <= N <= 50000, 0 <= K <= 10^9, 1 <= Q <= 50000)

第2至N + 1行：每行1个数，对应数组中的数（1 <= A[i] <= 10^9)

第N + 2至N + M + 1行：每行2个数l, r中间用空格分隔(0 <= l <= r < N)

Output

输出共Q行，对于Q条查询的结果

莫队 + bit/主席树
离散化的时候先预处理出所有的离散化值，不然会t

代码：

   //File Name: nod1290.cpp

   //Author: long

   //Mail: 736726758@qq.com

   //Created Time: 2016年09月16日 星期五 17时22分07秒

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <math.h>

 #define LL long long

 #define hash _hash_

 using namespace std;

 const int MAXN = ;

 int hash[MAXN * ],num[MAXN * ],top,tot;

 void hash_init(){

     sort(num+,num+top+);

     tot = ;

     hash[++tot] = num[];

     for(int i=;i<=top;i++)

         if(num[i] != num[i-])

             hash[++tot] = num[i];

 }

 int hash_find(int x){

     int l = ,r = tot,m;

     while(l <= r){

         m = l + r >> ;

         if(hash[m] < x) l = m + ;

         else r = m - ;

     }

     return l;

 }

 int a[MAXN],b[MAXN],c[MAXN],bel[MAXN],bit[MAXN * ],cur_l,cur_r,K;

 LL ans[MAXN],cur_ans;

 struct Query{

     int ql,qr,id;

 }que[MAXN];

 bool cmp(Query x,Query y){

     if(bel[x.ql] == bel[y.ql]) return x.qr < y.qr;

     return bel[x.ql] < bel[y.ql];

 }

 void update(int x,int add){

     for(int i=x;i<=tot;i+=i&-i)

         bit[i] += add;

 }

 int query(int x){

     int res = ;

     for(int i=x;i>;i-=i&-i)

         res += bit[i];

     return res;

 }

 int cal(int u){

     return query(c[u]) - query(b[u] - );

 }

 void update_l(int to_l){

     while(cur_l < to_l){

         update(a[cur_l],-);

         cur_ans -= cal(cur_l);

         cur_l++;

     }

     while(cur_l > to_l){

         cur_l--;

         cur_ans += cal(cur_l);

         update(a[cur_l],);

     }

 }

 void update_r(int to_r){

     while(cur_r < to_r){

         cur_r++;

         cur_ans += cal(cur_r);

         update(a[cur_r],);

     }

     while(cur_r > to_r){

         update(a[cur_r],-);

         cur_ans -= cal(cur_r);

         cur_r--;

     }

 }

 void solve(int n,int q){

     hash_init();

     for(int i=;i<=n;i++){

         b[i] = hash_find(a[i] - K);

         c[i] = hash_find(a[i] + K);

         a[i] = hash_find(a[i]);

     }

     memset(ans,,sizeof ans);

     int NUM = (int)sqrt(n + 0.5);

     for(int i=;i<=n;i++)

         bel[i] = (i - ) / NUM;

     sort(que+,que+q+,cmp);

     memset(bit,,sizeof bit);

     update(a[],);

     cur_l = cur_r = ;

     cur_ans = ;

     for(int i=;i<=q;i++){

         update_r(que[i].qr);

         update_l(que[i].ql);

         ans[que[i].id] = cur_ans;

     }

 }

 int main(){

     int n,q;

     while(~scanf("%d %d %d",&n,&K,&q)){

         top = ;

         for(int i=;i<=n;i++){

             scanf("%d",a + i);

             num[++top] = a[i];

             num[++top] = a[i] - K;

             num[++top] = a[i] + K;

         }

         for(int i=;i<=q;i++){

             scanf("%d %d",&que[i].ql,&que[i].qr);

             que[i].ql++,que[i].qr++,que[i].id = i;

         }

         solve(n,q);

         for(int i=;i<=q;i++)

             printf("%lld\n",ans[i]);

     }

     return ;

 }