JSCPC 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): 0 Accepted Submission(s): 0

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

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

Sample Output

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

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

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const int maxn = 57005;

int n, m, be[maxn], ans[maxn], c[maxn];
LL k, a[maxn], b[maxn], l[maxn], r[maxn];

struct node
{
    int l, r, id;
}q[maxn];

int cmp(node a, node b){
    return (be[a.l] ^ be[b.l]) ? be[a.l] < be[b.l] : ((be[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

int lowbit(int x){
    return x & (-x);
}

void add(int x, int num){
    if(!x) return ;
    while(x <= n){
        c[x] += num;
        x += lowbit(x);
    }
}

int sum(int x){
    int res = 0;
    if(x <= 0) return 0;
    while(x){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    scanf("%d %d %lld", &n, &m, &k);
    int size = sqrt(n);
    int bnum = ceil((double)n / size);
    for (int i = 1; i <= bnum; i++){
        for (int j = (i - 1) * size + 1; j <= i * size; j++) be[j] = i;
    }
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i - 1] = a[i];
    for (int i = 1; i <= m; i++){
        scanf("%d %d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m, cmp);
    sort(b, b + n);
    int pos = unique(b, b + n) - b;
    for (int i = 1; i <= n; i++){
        l[i] = lower_bound(b, b + pos, a[i] - k) - b + 1;
        r[i] = upper_bound(b, b + pos, a[i] + k) - b;
        a[i] = lower_bound(b, b + pos, a[i]) - b + 1;
    }
    int L = 1, R = 0, temp = 0;
    for (int i = 1; i <= m; i++){
        int ql = q[i].l, qr = q[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[q[i].id] = temp;

    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);

    return 0;
}
/**/

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