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

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1164 Accepted Submission(s): 421

Problem Description

Chika gives you an integer sequence

Input

The first line contains

。

Output

For each task, you need to print one line, including only one integer, representing the number of "friendly pairs" in the query interval.

Sample Input

7 5 3 2 5 7 5 1 5 6 6 6 1 3 4 6 2 4 3 4

Sample Output

0 2 1 3 1

Source

2019CCPC湖南全国邀请赛（广东省赛、江苏省赛）重现赛

解题思路：莫队维护区间，树状数组维护小于等于这个数的个数, 由于数很大要离散化.

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 
  8 typedef long long ll;
  9 
 10 int n,m,k,L,R;
 11 const int N=27007;
 12 int arr[N],brr[N],low[N],up[N],my[N],cnt[N];
 13 int ee[N],res;
 14 
 15 
 16 inline int read(){
 17     int x=0,f=1;
 18     char ch=getchar();
 19     while(ch<'0'||ch>'9'){
 20         if(ch=='-')
 21             f=-1;
 22         ch=getchar();
 23     }
 24     while(ch>='0'&&ch<='9'){
 25         x=(x<<1)+(x<<3)+(ch^48);
 26         ch=getchar();
 27     }
 28     return x*f;
 29 }
 30 
 31 int lowbits(int x){
 32     return x&(-x);
 33 }
 34 
 35 void add(int x,int num){
 36     while(x<27000){
 37         cnt[x]+=num;
 38         x+=lowbits(x);
 39     }
 40 }
 41 
 42 int sum(int x){
 43     int res=0;
 44     while(x){
 45         res+=cnt[x];
 46         x-=lowbits(x);
 47     }
 48     return res;
 49 }
 50 
 51 struct Node{
 52     int l,r,id,ans;
 53     bool operator<(const Node&X)const{
 54 //        if(ans!=X.ans) return ans<X.ans;
 55 //        return r<X.r;
 56         return (ans^X.ans)?l<X.l:(ans&1)?r<X.r:r>X.r;
 57     }
 58 }A[N];
 59 
 60 
 61 int main(){
 62     scanf("%d%d%d",&n,&m,&k);
 63     for(int i=1;i<=n;i++) scanf("%d",&arr[i]),brr[i]=arr[i];
 64     sort(arr+1,arr+1+n);
 65     int size=unique(arr+1,arr+1+n)-arr-1;
 66     for(int i=1;i<=n;i++){
 67         low[i]=lower_bound(arr+1,arr+1+size,brr[i]-k)-arr-1;  //比x小的
 68         up[i]=upper_bound(arr+1,arr+1+size,brr[i]+k)-arr-1;  //等于y的
 69         my[i]=lower_bound(arr+1,arr+1+size,brr[i])-arr;
 70     }
 71     int big=sqrt(n);
 72     for(int i=1;i<=m;i++){
 73         A[i].l=read(),A[i].r=read();
 74         A[i].id=i;A[i].ans=(A[i].l-1)/big+1;    //分块在哪个块
 75     }
 76     sort(A+1,A+1+m);
 77     L=1,R=0;
 78     for(int i=1;i<=m;i++){
 79         while(L<A[i].l){
 80             add(my[L],-1);
 81             res-=sum(up[L])-sum(low[L]);
 82             L++;
 83         }
 84         while(L>A[i].l){
 85             L--;
 86             res+=sum(up[L])-sum(low[L]);
 87             add(my[L],1);
 88         }
 89         while(R>A[i].r){
 90             add(my[R],-1);
 91             res-=sum(up[R])-sum(low[R]);
 92             R--;
 93         }
 94         while(R<A[i].r){
 95             R++;
 96             res+=sum(up[R])-sum(low[R]);
 97             add(my[R],1);
 98         }
 99         ee[A[i].id]=res;
100     }
101     for(int i=1;i<=m;i++) printf("%d
",ee[i]);
102     return 0;
103 }

View Code

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

相关推荐