Description

求区间内有多少对 \((i,j)\) 满足 \(|a_i - a_j| \leq k\)

Solution

可以莫队做（万能的莫队）

只需要考虑加入一个数会产生多少贡献即可

离散化的时候把 \(a_i,a_i - k, a_i+k\) 全部放进去。

加入一个数的时候只需要维护 \([a_i - k,a_i+k]\) 有多少个数，并且把 \(a_i\) 这个位置加上 1

删除亦然。这个可以用树状数组方便地维护。

具体实现的时候，因为树状数组是 sum(r) - sum(l-1) ，所以可以直接把 \(a_i,a_i - k-1, a_i+k\) 放进去离散化，求贡献就不用 -1 了

总复杂度 \(O(n \sqrt n \log n)\)

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 100050;

int n, k, q, blo, c[N * 2], now, ans[N], tmp[2 * N], MX;

struct Query {

  int l, r, id;

  inline bool operator < (const Query &x) const {

    return l / blo == x.l / blo ? r < x.r : l / blo < x.l / blo;

  }

} Q[N];

struct node {

  int id, lk, rk, val, se;

} a[N];

inline int lb(int x) { return x & (-x); }

inline void add(int x, int d) {

  for(int i = x; i <= MX; i += lb(i))

    c[i] += d;

}

inline int sum(int x) {

  int ret = 0;

  for(int i = x; i; i -= lb(i))

    ret += c[i];

  return ret;

}

inline void ADD(int x) {

  now += sum(a[x].rk) - sum(a[x].lk);

  add(a[x].val, 1);

}

inline void DEL(int x) {

  add(a[x].val, -1);

  now -= sum(a[x].rk) - sum(a[x].lk);

}

int main() { int cnt = 0;

  scanf("%d %d %d", &n, &k, &q); blo = sqrt(q);

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

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

    a[i].lk = a[i].val - k - 1, a[i].rk = a[i].val + k;

    tmp[++cnt] = a[i].lk;

    tmp[++cnt] = a[i].rk;

    tmp[++cnt] = a[i].val;

  } sort(tmp + 1, tmp + cnt + 1);

  int len = unique(tmp + 1, tmp + cnt + 1) - tmp - 1;

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

    a[i].val = lower_bound(tmp + 1, tmp + len + 1, a[i].val) - tmp;

    a[i].lk = lower_bound(tmp + 1, tmp + len + 1, a[i].lk) - tmp;

    a[i].rk = lower_bound(tmp + 1, tmp + len + 1, a[i].rk) - tmp;

    MX = max(a[i].rk, MX);

  }

  for(int i = 1; i <= q; i++) {

    scanf("%d %d", &Q[i].l, &Q[i].r); Q[i].id = i;

    Q[i].l++, Q[i].r++;

  } sort(Q + 1, Q + q + 1);

  int L = 1, R = 0;

  for(int i = 1; i <= q; i++) {

    int l = Q[i].l, r = Q[i].r;

    while(L > l) ADD(--L);

    while(R < r) ADD(++R);

    while(L < l) DEL(L++);

    while(R > r) DEL(R--);

    ans[Q[i].id] = now;

  }

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

  return 0;

}