2019CCPC湖南全国邀请赛（广东省赛、江苏省赛） C.Chika and Friendly Pairs

Problem Description

Chika gives you an integer sequence a1,a2,…,an and m tasks. For each task, you need to answer the number of "friendly pairs" in a given interval.

friendly pair: for two integers ai and aj, if i<j and the absolute value of ai−aj is no more than a given constant integer K, then (i,j) is called a "friendly pair".A friendly pair (i,j) in a interval [L,R] should satisfy L≤i<j≤R.

Input

The first line contains 3 integers n (1≤n≤27000), m (1≤m≤27000) and K (1≤K≤109), representing the number of integers in the sequence a, the number of tasks and the given constant integer.
The second line contains n non-negative integers, representing the integers in the sequence a. Every integer of sequence a is no more than 109.
Then m lines follow, each of which contains two integers L, R (1≤L≤R≤n). The meaning is to ask the number of "friendly pairs" in the interval [L,R]。

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

思路：莫队加树状数组

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
const int maxn=30050;
struct Q{
    int l,r,id,blk;
};
bool operator < (Q a, Q b){
    return a.blk<b.blk||a.blk==b.blk&&a.r<b.r;
}
int a[maxn],_a[maxn],val[maxn];
int l0[maxn],r0[maxn],res[maxn];
int c[maxn];
int n,m,k,num,blk;
Q q[maxn];

int lowbit(int x){
    return x&-x;
}
void add(int k,int val){
    while(k<=num){
        c[k]+=val;k+=lowbit(k);
    }
}
int query(int k){
    int sum=0;
    while(k){
        sum+=c[k];k-=lowbit(k);
    }
    return sum;
}
void solve(){
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        _a[i]=a[i];
    }
    sort(a+1,a+n+1);
    num=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;i++)   val[i]=lower_bound(a+1,a+num+1,_a[i])-a;
    int l=1,r=1;
    for(int i=1;i<=num;i++){
        while(a[i]-a[l]>k)  l++;
        while(r<=num&&a[r]-a[i]<=k)  r++;
        r--;
        l0[i]=l;r0[i]=r;
    }
    blk=(int)sqrt(n);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&l,&r);
        q[i].l=l;q[i].r=r;q[i].id=i;q[i].blk=l/blk;
    }
    sort(q+1,q+m+1);
    l=1,r=0;
    int sum=0;
    for(int i=1;i<=m;i++){
        while(l<q[i].l){
            int _val=val[l++];
            add(_val,-1);sum-=query(r0[_val])-query(l0[_val]-1);
        }
        while(l>q[i].l){
            int _val=val[--l];
            sum+=query(r0[_val])-query(l0[_val]-1);add(_val,1);
        }
        while(r<q[i].r){
            int _val=val[++r];
            sum+=query(r0[_val])-query(l0[_val]-1);add(_val,1);
        }
        while(r>q[i].r){
            int _val=val[r--];
            add(_val,-1);sum-=query(r0[_val])-query(l0[_val]-1);
        }
        res[q[i].id]=sum;
    }
    for(int i=1;i<=m;i++)   printf("%d\n",res[i]);
}
int main(){
    solve();
    return 0;
}
/*
7 5 3
2 5 7 5 1 5 6
6 6
1 3
4 6
2 4
3 4
*/