HDU6534 [CCPC2019 湘潭邀请赛] Chika and Friendly Pairs

Description

给定长度为 nn 的序列 aa (0ai109)\left(0\leq a_i\leq10^9\right)mm 次询问 (1n,m2.7×104)\left(1\leq n,m\leq2.7\times10^4\right) .
给定常数 KK (1K109)\left(1\leq K\leq10^9\right) ,询问以 (L,R)\left(L,R\right) (1LRn)\left(1\leq L\leq R\leq n\right) 的形式给出。
询问 (L,R)\left(L,R\right) 表示求

ans=i=LRj=i+1R[aiajK]ans=\sum_{i=L}^R\sum_{j=i+1}^R\left[\left|a_i-a_j\right|\leq K\right]


Solution

将序列 aa 和集合 {aiK,ai+Ki[1,n]}\left\{a_i-K,a_i+K\big|i\in\left[1,n\right]\right\} 中的元素 离散化
考虑 莫队 ++ 树状数组 ,询问区间移动时:

  • 若加入一个元素 xx ,则:
    • 先求区间 [xK,x+K]\left[x-K,x+K\right] 中的元素数并累加到答案中。
    • 再将 xx 加入树状数组中即可。
  • 若删去一个元素 xx ,则:
    • 先将 xx 从树状数组中删去。
    • 再求区间 [xK,x+K]\left[x-K,x+K\right] 中的元素数并从答案中减去即可。

时间复杂度:O((n+m)nlogn)\mathcal O\left(\left(n+m\right)\sqrt n\log n\right) .


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

struct qry {
int x, l, r, li;
bool operator<(const qry &t) const {
return li == t.li ? r < t.r : l < t.l;
}
};

const int N = 2.7e4 + 5;
int n, m, k, a[N];
qry q[N];
int ct, b[N], idx[N], low[N], upp[N];
int sq, l, r, cnt, bit[N], ans[N];

void solve(void);
void add(int x);
void del(int x);
void modify(int x, int d);
int query(int x);
int lowbit(int x);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d%d%d", &n, &m, &k), sq = sqrt(n), l = 1;
for (int i = 1; i <= n; i++) scanf("%d", a + i), b[i] = a[i];
sort(b + 1, b + n + 1), ct = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++) {
idx[i] = lower_bound(b + 1, b + ct + 1, a[i]) - b;
low[i] = lower_bound(b + 1, b + ct + 1, a[i] - k) - b;
upp[i] = upper_bound(b + 1, b + ct + 1, a[i] + k) - b - 1;
}
for (int i = 1; i <= m; i++)
scanf("%d%d", &q[i].l, &q[i].r), q[i].x = i, q[i].li = q[i].l / sq;
sort(q + 1, q + m + 1);
for (int i = 1; i <= m; i++) {
while (r < q[i].r) add(++r);
while (r > q[i].r) del(r--);
while (l < q[i].l) del(l++);
while (l > q[i].l) add(--l);
ans[q[i].x] = cnt;
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}

inline void add(int x) {
cnt += query(upp[x]) - query(low[x] - 1), modify(idx[x], 1);
}

inline void del(int x) {
modify(idx[x], -1), cnt -= query(upp[x]) - query(low[x] - 1);
}

void modify(int x, int d) {
for (; x <= ct; x += lowbit(x)) bit[x] += d;
}

int query(int x) {
int ans = 0;
for (; x; x -= lowbit(x)) ans += bit[x];
return ans;
}

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

Tsukkomi

初学莫队,练练手 qwq

Welcome to my other publishing channels