HDU - 6534 Chika and Friendly Pairs

这个题其实也是很简单的莫队，题目要求是给一个序列，询问l-r区间内部，找到有多少对答案满足 i < j 并且

| a[ i ] -a[ j ] | <=k 也就是有多少对，满足差值小于k的个数。

把这个式子展开，其实就是-k<= a[ i ] -a [ j ] <= k 也就是 a[ j ] -k <= a[ i ] <= a[ j ] + k，也就是说，对于某个 j 位置，我们需要在询问的区间内，找到 i < j 并且在[ a[j] -k ,a[j] +k ] 范围中的数的个数，这个其实可以通过树状数组区间查询即可。

但是对于k来说，太大了，树状数组也开不下，所以我们要进行离散化，把a[i],a[i]+k,a[i]-k位置存下来即可（老套路了）保证每个位置都能找得到，然后区间查询即可，然后每次算贡献即可。

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

const int maxx = 2e5+;

int block;

int a[maxx];

std::vector<int>vx;

int sum[maxx];

int ans[maxx];

int num;

int n,m,k;

struct node{

  int l,r;

  int id;

  friend bool operator < (const node &a,const node &b){

      if(a.l/block==b.l/block){

          return a.r<b.r;

      }

      return a.l/block<b.l/block;

  }

}q[maxx];

int low[maxx];

int up[maxx];

int p[maxx];

int lowbit(int x){

  return x&(-x);

}

void add(int x,int w){

   for(int i=x;i<=*n;i+=lowbit(i)){

     sum[i]+=w;

   }

   return ;

}

int getsum(int x){

   int s=;

   for(int i=x;i;i-=lowbit(i)){

       s+=sum[i];

   }

   return s;

}

void add(int x){

   num+=getsum(up[x])-getsum(low[x]-);

   add(p[x],);

}

void del(int x){

   add(p[x],-);

   num-=getsum(up[x])-getsum(low[x]-);

}

int main(){

  while(~scanf("%d%d%d",&n,&m,&k)){

     block=sqrt(n);

     memset(sum,,sizeof(sum));

     memset(ans,,sizeof(ans));

     vx.clear();

     ///绝对值小于等于K

     for (int i=;i<=n;i++){

        scanf("%d",&a[i]);

        vx.push_back(a[i]);

        vx.push_back(a[i]+k);

        vx.push_back(a[i]-k);

     }

     num=;

     sort(vx.begin(),vx.end());

     vx.erase(unique(vx.begin(),vx.end()),vx.end());

     int sz=vx.size();

     for(int i=;i<=n;i++){

        p[i]=lower_bound(vx.begin(),vx.end(),a[i])-vx.begin()+;

        low[i]=lower_bound(vx.begin(),vx.end(),a[i]-k)-vx.begin()+;

        up[i]=lower_bound(vx.begin(),vx.end(),a[i]+k)-vx.begin()+;

     }

     for(int i=;i<=m;i++){

       scanf("%d%d",&q[i].l,&q[i].r);

       q[i].id=i;

     }

     sort(q+,q++m);

     int l=,r=;

     num=;

     for(int i=;i<=m;i++){

        while(l<q[i].l)del(l),l++;

      //  cout<<num<<" ";

        while(l>q[i].l)l--,add(l);

      //  cout<<num<<" ";

        while(r<q[i].r)r++,add(r);

       // cout<<num<<" ";

        while(r>q[i].r)del(r),r--;

      //  cout<<num<<" "<<endl;

        ans[q[i].id]=num;

     }

    for(int i=;i<=m;i++){

        printf("%d\n",ans[i]);

    }

  }

  return ;

}

巴特西

HDU - 6534 Chika and Friendly Pairs

最新文章

热门文章