首页 > 代码库 > 51nod 1290 Counting Diff Pairs 莫队 + bit
51nod 1290 Counting Diff Pairs 莫队 + bit
一个长度为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
代码：
1 2 //File Name: nod1290.cpp 3 //Author: long 4 //Mail: 736726758@qq.com 5 //Created Time: 2016年09月16日 星期五 17时22分07秒 6 7 #include <stdio.h> 8 #include <string.h> 9 #include <iostream> 10 #include <algorithm> 11 #include <math.h> 12 #define LL long long 13 #define hash _hash_ 14 using namespace std; 15 const int MAXN = 50010; 16 int hash[MAXN * 3],num[MAXN * 3],top,tot; 17 void hash_init(){ 18 sort(num+1,num+top+1); 19 tot = 0; 20 hash[++tot] = num[1]; 21 for(int i=2;i<=top;i++) 22 if(num[i] != num[i-1]) 23 hash[++tot] = num[i]; 24 } 25 int hash_find(int x){ 26 int l = 1,r = tot,m; 27 while(l <= r){ 28 m = l + r >> 1; 29 if(hash[m] < x) l = m + 1; 30 else r = m - 1; 31 } 32 return l; 33 } 34 int a[MAXN],b[MAXN],c[MAXN],bel[MAXN],bit[MAXN * 3],cur_l,cur_r,K; 35 LL ans[MAXN],cur_ans; 36 struct Query{ 37 int ql,qr,id; 38 }que[MAXN]; 39 bool cmp(Query x,Query y){ 40 if(bel[x.ql] == bel[y.ql]) return x.qr < y.qr; 41 return bel[x.ql] < bel[y.ql]; 42 } 43 void update(int x,int add){ 44 for(int i=x;i<=tot;i+=i&-i) 45 bit[i] += add; 46 } 47 int query(int x){ 48 int res = 0; 49 for(int i=x;i>0;i-=i&-i) 50 res += bit[i]; 51 return res; 52 } 53 int cal(int u){ 54 return query(c[u]) - query(b[u] - 1); 55 } 56 void update_l(int to_l){ 57 while(cur_l < to_l){ 58 update(a[cur_l],-1); 59 cur_ans -= cal(cur_l); 60 cur_l++; 61 } 62 while(cur_l > to_l){ 63 cur_l--; 64 cur_ans += cal(cur_l); 65 update(a[cur_l],1); 66 } 67 } 68 void update_r(int to_r){ 69 while(cur_r < to_r){ 70 cur_r++; 71 cur_ans += cal(cur_r); 72 update(a[cur_r],1); 73 } 74 while(cur_r > to_r){ 75 update(a[cur_r],-1); 76 cur_ans -= cal(cur_r); 77 cur_r--; 78 } 79 } 80 void solve(int n,int q){ 81 hash_init(); 82 for(int i=1;i<=n;i++){ 83 b[i] = hash_find(a[i] - K); 84 c[i] = hash_find(a[i] + K); 85 a[i] = hash_find(a[i]); 86 } 87 memset(ans,0,sizeof ans); 88 int NUM = (int)sqrt(n + 0.5); 89 for(int i=1;i<=n;i++) 90 bel[i] = (i - 1) / NUM; 91 sort(que+1,que+q+1,cmp); 92 memset(bit,0,sizeof bit); 93 update(a[1],1); 94 cur_l = cur_r = 1; 95 cur_ans = 0; 96 for(int i=1;i<=q;i++){ 97 update_r(que[i].qr); 98 update_l(que[i].ql); 99 ans[que[i].id] = cur_ans;100 }101 }102 int main(){103 int n,q;104 while(~scanf("%d %d %d",&n,&K,&q)){105 top = 0;106 for(int i=1;i<=n;i++){107 scanf("%d",a + i);108 num[++top] = a[i];109 num[++top] = a[i] - K;110 num[++top] = a[i] + K;111 }112 for(int i=1;i<=q;i++){113 scanf("%d %d",&que[i].ql,&que[i].qr);114 que[i].ql++,que[i].qr++,que[i].id = i;115 }116 solve(n,q);117 for(int i=1;i<=q;i++)118 printf("%lld\n",ans[i]);119 }120 return 0;121 }
51nod 1290 Counting Diff Pairs 莫队 + bit
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。