51nod 1290 Counting Diff Pairs

问题描述

一个长度为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条查询的结果。

Input示例

5 2 3
1
3
4
3
0
0 1
1 3
0 4

Output示例

1
3
6

solution:

假设已经求出了（l，r）的结果，我们能不能快速得求出相邻的询问即（l+1，r）、（l-1，r）、（l，r+1）、（l，r-1）？显然是可以的。如果要加入一个值，对答案的影响是加上（l，r）中与$a_{r+1}$差小于等于k的值的个数，能不能维护这个操作？树状数组完全可以胜任。单点插入、删除时间复杂度O（lg n），更新答案的时间复杂度也是O（lg n）。
满足了这个性质，就可以使用莫队算法了。
讲询问区间看成一个在平面直角坐标系上的点，为了求出所有的询问，最优的做法是求出最小曼哈顿生成树，可是好麻烦……，我们可以把平面根据x坐标分块，分块大法好，对于同一块中的点，根据y坐标排序，然后对于同一块中的点，从下向上依次移动，对于前一块的最后一个点和下一块的第一个点，暴力解决。
我们来计算一下时间复杂度，对于同一块中的移动，次数O(n)，每次O（$\sqrt{n}$），所以是O(n$\sqrt{n}$).再来算跨块的移动，次数O（$\sqrt{n}$），每次O（n），所以也是(n$\sqrt{n}$)。再加上树状数组的O（lg n），所以总的时间复杂度是O（n $\sqrt{n}$ lg n）。
对了，这道题要离散化

code:

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
struct node{int x,y,z;
}ques[50005];
bool cmp1(node x,node y){return x.x<y.x||x.x==y.x&&x.y<y.y;
}
bool cmp2(node x,node y){return x.y<y.y||x.y==y.y&&x.x<y.x;
}
int n,k,q,bit[50005],a[50005],b[50005],cnt,num,belong[50005],l[50005],r[50005],nowx,nowy,Max[500005],Min[500005];
int lowbit(int x){return x&-x;
}
void add(int x,int y){while(x<=cnt){bit[x]+=y;x+=lowbit(x);}
}
int query(int x){int ans=0;while(x){ans+=bit[x];x-=lowbit(x);}return ans;
}
long long ans,aa[50005];
int main(){scanf("%d%d%d",&n,&k,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]++;b[i]=a[i];}sort(b+1,b+1+n);cnt=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++){int tmp=a[i];a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;if(!Min[a[i]])Min[a[i]]=lower_bound(b+1,b+1+cnt,tmp-k)-b;if(!Max[a[i]])Max[a[i]]=upper_bound(b+1,b+1+cnt,tmp+k)-b-1;}for(int i=1;i<=q;i++){scanf("%d%d",&ques[i].x,&ques[i].y);ques[i].x++;ques[i].y++;ques[i].z=i;}sort(ques+1,ques+1+q,cmp1);num=sqrt(n);for(int i=1;i<=q;i++){int x=(ques[i].x-1)/num+1;if(x>num)x=num;if(!l[x])l[x]=i;r[x]=i;}nowx=1;nowy=1;add(a[1],1);ans=0;for(int i=1;i<=num;i++){if(!l[i])continue;sort(ques+l[i],ques+r[i]+1,cmp2);for(int j=l[i];j<=r[i];j++){while(nowy<ques[j].y){ans+=(long long)query(min(cnt,Max[a[nowy+1]]))-query(max(0,Min[a[nowy+1]]-1));add(a[nowy+1],1);nowy++;}while(nowx>ques[j].x){ans+=(long long)query(min(cnt,Max[a[nowx-1]]))-query(max(0,Min[a[nowx-1]]-1));add(a[nowx-1],1);nowx--;}while(nowy>ques[j].y){add(a[nowy],-1);ans-=(long long)query(min(cnt,Max[a[nowy]]))-query(max(0,Min[a[nowy]]-1));nowy--;}while(nowx<ques[j].x){add(a[nowx],-1);ans-=(long long)query(min(cnt,Max[a[nowx]]))-query(max(0,Min[a[nowx]]-1));nowx++;}   aa[ques[j].z]=ans;}   }for(int i=1;i<=q;i++)printf("%lld\n",aa[i]);return 0;
}