HDU6534 Chika and Friendly Pairs（离散化+树状数组+莫队）

矫情吗；* 2021-11-22 10:38 255阅读 0赞

## 题意：给出一个含有n个元素的数列a和k值，询问m次，每次询问给出L，R，输出\[L，R\]中friendly pair的总个数。friendly pair**：**对于数列位置i < j，有丨 a\[i\] - a\[j\] 丨<= k，则相当于一个friendly pair。 ##

## 分析：输入n个a\[i\]，对 a\[i\]-k, a\[i\], a\[i\]+k进行离散化+去重，存到b数组中 ，预处理 a\[i\]-k, a\[i\], a\[i\]+k 在b数组中的位置，分别存到down, a, up数组中，输入m个区间，存到结构体中，按照莫队算法进行排序，之后用树状数组维护a\[i\]的位置，两次query查询a\[i\]-k到a\[i\]+k区间中有多少数。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 3e4;
    int c[N*3], a[N], b[N*3], up[N], down[N];
    int n, m, k, belong[N], ans[N];
    struct node{
    	int id, l, r;
    }no[N];
    bool cmp(node a, node b){
    	if(belong[a.l]==belong[b.l]) return a.r<b.r;
    	return belong[a.l]<belong[b.l];
    }
    int lowbit(int x){
    	return x&(-x);
    }
    void add(int x, int val){
    	while(x<=n*3){
    		c[x]+=val;
    		x+=lowbit(x);
    	}
    }
    int query(int x){
    	int ret=0;
    	while(x){
    		ret+=c[x];
    		x-=lowbit(x);
    	}
    	return ret;
    }
    int main()
    {
    	int i, bk, tot=0;
    	scanf("%d%d%d",&n,&m,&k);
    	bk=sqrt(n);
    	for(i=1;i<=n;++i) belong[i]=(i-1)/bk+1;
    	for(i=1;i<=n;++i){
    		scanf("%d",&a[i]);
    		b[++tot]=a[i]-k;
    		b[++tot]=a[i];
    		b[++tot]=a[i]+k;
    	}
    	sort(b+1,b+tot+1);
    	tot=unique(b+1,b+tot+1)-b-1;
    	for(i=1;i<=n;++i){
    		up[i]=lower_bound(b+1,b+tot+1,a[i]+k)-b;
    		down[i]=lower_bound(b+1,b+tot+1,a[i]-k)-b;
    		a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    	}
    	for(i=1;i<=m;++i)
    		scanf("%d%d",&no[i].l,&no[i].r), no[i].id=i;
    	sort(no+1,no+m+1,cmp);
    	int l=no[1].l, r=l-1, sum=0;
    	for(i=1;i<=m;++i){
    		while(r<no[i].r){
    			++r;
    			sum+=query(up[r])-query(down[r]-1);
    			add(a[r],1);
    		}
    		while(l>no[i].l){
    			--l;
    			sum+=query(up[l])-query(down[l]-1);
    			add(a[l],1);
    		}
    		while(r>no[i].r){
    			add(a[r],-1);
    			sum-=query(up[r])-query(down[r]-1);
    			--r;
    		}
    		while(l<no[i].l){
    			add(a[l],-1);
    			sum-=query(up[l])-query(down[l]-1);
    			++l;
    		}
    		ans[no[i].id]=sum;
    	}
    	for(i=1;i<=m;++i) printf("%d\n",ans[i]);
    	return 0;
    }