给一串数字，叫你算L到R之间绝对值为k的数对有多少，线段树不行，亲手超的时，得用树状数组而且还要优化一下离散化。
a[]数组是原本数列的数组，b是a经过排序去重后得到的数组，树状数组c[i]存的是小于等于b[i]的数出现的次数，莫队的时候区间扩大时，被扩充进来的数 x 对于答案的贡献就是当前区间内，所有在 x-k 到 x+k 之间数字出现的次数，直接query（上界）- query（下界）就是对答案的贡献，上下界 up 和 low 数组 表示 第 i 个数其 b[i]+k 和 b[i]-k-1 在 b 数组中的位置，如果这里每次都用二分查找其位置会超时，所以在这里用两个数组把他们存起来
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#include <set>
#include <list>
#include <iostream>
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std
;
const int mod
=1e9+7;
const int INF
=1e9+7;
const int maxn
=27000+50;
struct Mo
{
int l
,r
,id
;
}q
[maxn
];
int n
,m
,k
,block
,len
;
int a
[maxn
],b
[maxn
],c
[maxn
],ans
[maxn
],up
[maxn
],low
[maxn
];
int sear(int x
)
{
int l
=1,r
=len
-1;
while(l
<=r
){
int mid
=(l
+r
)>>1;
if(b
[mid
]==x
)return mid
;
if(b
[mid
]<x
)l
=mid
+1;
if(b
[mid
]>x
)r
=mid
;
}
}
int cmp(Mo a
,Mo b
)
{
if(a
.l
/block
==b
.l
/block
)return a
.r
<b
.r
;
return a
.l
<b
.l
;
}
int lowbit(int x
)
{
return x
&(-x
);
}
void Update(int x
,int C
)
{
for(int i
=x
;i
<=maxn
;i
+=lowbit(i
)){
c
[i
]+=C
;
}
}
int Query(int x
)
{
int ANS
=0;
for(int i
=x
;i
>0;i
-=lowbit(i
)){
ANS
+=c
[i
];
}
return ANS
;
}
int main()
{
scanf("%d%d%d",&n
,&m
,&k
);
block
=sqrt(n
);
for(int i
=1;i
<=n
;i
++)scanf("%d",&a
[i
]),b
[i
]=a
[i
];
sort(b
+1,b
+1+n
);
len
=unique(b
+1,b
+1+n
)-b
;
for(int i
=1;i
<=n
;i
++){
int x
=lower_bound(b
+1,b
+len
,a
[i
]-k
)-b
;
int y
=upper_bound(b
+1,b
+len
,a
[i
]+k
)-b
;
low
[i
]=x
-1;
up
[i
]=y
-1;
}
for(int i
=1;i
<=m
;i
++)scanf("%d%d",&q
[i
].l
,&q
[i
].r
),q
[i
].id
=i
;
sort(q
+1,q
+1+m
,cmp
);
int ret
=0;
int l
=1,r
=0;
for(int i
=1;i
<=m
;i
++){
while(r
<q
[i
].r
){
ret
+=Query(up
[r
+1])-Query(low
[r
+1]);
Update(sear(a
[r
+1]),1);
r
++;
}
while(r
>q
[i
].r
){
Update(sear(a
[r
]),-1);
ret
-=Query(up
[r
])-Query(low
[r
]);
r
--;
}
while(l
<q
[i
].l
){
Update(sear(a
[l
]),-1);
ret
-=Query(up
[l
])-Query(low
[l
]);
l
++;
}
while(l
>q
[i
].l
){
ret
+=Query(up
[l
-1])-Query(low
[l
-1]);
Update(sear(a
[l
-1]),1);
l
--;
}
ans
[q
[i
].id
]=ret
;
}
for(int i
=1;i
<=m
;i
++)printf("%d\n",ans
[i
]);
return 0;
}
