Description
一个长度为N的正整数数组A，给出一个数K以及Q个查询，每个查询包含2个数l和r，对于每个查询输出从A[i]到A[j]中，有多少对数，abs(A[i] - A[j]) <= K(abs表示绝对值)。
2 <= N <= 50000，0 <= K <= 10^9，1 <= Q <= 50000，1 <= A[i] <= 10^9
Solution
先把数字离散化，对于每个离散化后的数，求出它能满足条件的离散化后权值区间。
然后，就莫队+树状数组。
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
#define ll long long
using namespace std;
const int N=50010;
struct node{int x,wz,t;
}b[N];
struct md{int l,r,bl,wz;
}c[N];
int a[N],bl[N],tr[N];
ll an[N];
int L[N],R[N];
int m=0,n,k;
bool cmp(node x,node y){return x.x<y.x;
}
bool cmpmd(md x,md y){return x.bl<y.bl || (x.bl==y.bl && x.r<y.r);
}
void add(int x,int t){for(;x<=m;x+=x&-x) tr[x]+=t;
}
int sum(int x){int s=0;for(;x;x-=x&-x) s+=tr[x];return s;
}
int min(int x,int y){return x<y?x:y;
}
int get(int x){return sum(R[x])-sum(L[x]-1);
}
void pre(){sort(b+1,b+n+1,cmp);b[1].t=a[b[1].wz]=++m;fo(i,2,n){int t=(b[i].x!=b[i-1].x?++m:m);b[i].t=a[b[i].wz]=t;}int l=1,r=1;fo(i,1,n){while(l<i && b[i].x-b[l].x>k) l++;while(r<n && b[r+1].x-b[i].x<=k) r++;L[b[i].t]=b[l].t,R[b[i].t]=b[r].t;}
}
int main()
{int q;scanf("%d %d %d",&n,&k,&q);fo(i,1,n) scanf("%d",&b[i].x),b[i].wz=i;pre();int _n=0,tt=1;for(;(_n+1)*(_n+1)<=n;_n++);fo(i,1,n) bl[i]=tt,i%_n==0?tt++:tt;fo(i,1,q) scanf("%d %d",&c[i].l,&c[i].r),c[i].l++,c[i].r++,c[i].bl=bl[c[i].l],c[i].wz=i;sort(c+1,c+q+1,cmpmd);int l=1,r=1;ll ans=0;add(a[1],1);fo(i,1,q){int l1=c[i].l,r1=c[i].r;while(r<r1) ans+=get(a[++r]),add(a[r],1);while(l<l1) add(a[l],-1),ans-=get(a[l++]);while(l>l1) ans+=get(a[--l]),add(a[l],1);while(r>r1) add(a[r],-1),ans-=get(a[r--]);an[c[i].wz]=ans;}fo(i,1,q) printf("%lld\n",an[i]);
}