Chika and Friendly Pairs

http://acm.hdu.edu.cn/showproblem.php?pid=6534

题意：给你一个序列，多次询问，每次让你回答一个区间中差的绝对值不超过一个给定常数K的元素对数。

题解：对序列中的所有元素以及这些元素+K，-K后的值进行离散化。 然后使用莫队算法，在莫队算法的端点移动过程中，新加入一个元素x的过程中，将其插入树状数组，查询[x-K,x+K]范围的元素数即可。删除一个元素的过程与其类似。

C++版本一

题解：莫队+树状数组+离散化

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l[N],r[N],u,v;
int ans[N],cnt,flag,temp,tot;
int a[N],b[N],c[N],be[N];
char str;
struct node{
    int l,r,id;
    bool operator <(const node &S)const{
        return (be[l] ^ be[S.l]) ? be[l] < be[S.l] : ((be[l] & 1) ? r < S.r : r > S.r);
    }
}e[N];
int tree[N];
void add(int x,int C){
    for(int i=x;i<=tot;i+=i&-i){
        tree[i]+=C;
    }
}
int sum(int x){
    int res=0;
    for(int i=x;i>0;i-=i&-i){
        res+=tree[i];
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d%d",&n,&m,&k);
    int sz = sqrt(n);
    int bnum = ceil((double)n / sz);
    for (int i = 1; i <= bnum; i++){
        for (int j = (i - 1) * sz + 1; j <= i * sz; j++)
            be[j] = i;
    }
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    c[1]=b[1];
    tot=1;
    for(int i=2;i<=n;i++)if(b[i-1]!=b[i])c[++tot]=b[i];
    for(int i=1;i<=m;i++){
        scanf("%d%d",&e[i].l,&e[i].r);
        e[i].id=i;
    }
    sort(e+1,e+m+1);
    for (int i = 1; i <= n; i++){
        l[i] = lower_bound(c+1,c+tot+1, a[i] - k) - c  ;
        r[i] = upper_bound(c+1,c+tot+1, a[i] + k) - c - 1;
        a[i] = lower_bound(c+1,c+tot+1, a[i]) - c  ;
    }
    int L = 1, R = 0, temp = 0;
    for (int i = 1; i <= m; i++){
        int ql = e[i].l, qr = e[i].r;
        while(L < ql){
            add(a[L], -1);
            temp -= sum(r[L]) - sum(l[L] - 1);
            L++;
        }
        while(L > ql){
            L--;
            temp += sum(r[L]) - sum(l[L] - 1);
            add(a[L], 1);
        }
        while(R < qr){
            R++;
            temp += sum(r[R]) - sum(l[R] - 1);
            add(a[R], 1);
        }
        while(R > qr){
            add(a[R], -1);
            temp -= sum(r[R]) - sum(l[R] - 1);
            R--;
        }
        ans[e[i].id] = temp;
        //cout<<L<<" "<<R<<endl;
        //cout<<temp<<endl;
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<endl;
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

/**/
 
/*
5 5 3
2 5 7 1 3
6 6
1 3
2 4
1 5
2 3
*/