【树状数组 莫队】2019CCPC湖南全国邀请赛 C - Chika and Friendly Pairs
2021-05-06 14:16:00 # ACM

题链

给你一个长度为$n$的序列，有$m$次查询操作，每次查询$[L,R]$区间的友好对的个数。

友好对的定义：满足$i$ < $j$,且$|a_i-a_j|<=K$。

考虑每添加一个元素，计算该元素范围内$[x-k,x+k]$有多少个数（对树状数组来一发询问即可 $query(r) - query(l-1)$ ），加上该贡献；

离散所给数组，将$a[i]-k$和$a[i]+k$也加入，也离散；

用树状数组以及莫队解决

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;
#define MS 27009
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define ll long long
#define MAXN 20000000000
#define mod 1000000007

LL n,m,k;
LL p[MS*3]; 
LL a[MS];
LL b[MS*3],tb;
struct node{
	int l,r,id;
}ask[MS];
LL unit;
LL ac[MS];

struct nod{
	int pos,posl,posr;
}apos[MS];

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

bool cmp(node t1,node t2){
	if(t1.l/unit == t2.l/unit) return t1.r < t2.r;
	return t1.l/unit < t2.l/unit;
}

int getposb(LL x){
	if(x < 0) return 0;
	return lower_bound(b+1,b+tb+1,x)-b;
}

void add(int pos,LL val){
	for(;pos<=tb;pos+=lowbit(pos)) p[pos] += val;
}

LL getnum(int pos){
	LL ansl = 0;
	LL ansr = 0;
	int posl = apos[pos].posl-1;
	int posr = apos[pos].posr;
	for(;posl>0;posl-=lowbit(posl)) ansl += p[posl];
	for(;posr>0;posr-=lowbit(posr)) ansr += p[posr];
	return ansr - ansl - 1ll;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		b[++tb] = a[i];
		if(a[i]-k>0) b[++tb] = a[i]-k;
		b[++tb] = a[i]+k;
	}
	sort(b+1,b+tb+1);
	LL h = tb;
	tb = 1;
	for(int i=2;i<=h;i++){
		if(b[i] != b[i-1]) b[++tb] = b[i];
	}
	
	for(int i=1;i<=n;i++){
		int pos = getposb(a[i]);
		int posl = getposb(a[i]-k);
		int posr = getposb(a[i]+k);
		apos[i] = {pos,posl,posr};
	}
	
	for(int i=1;i<=m;i++){
		int l,r;
		cin >> l >> r;
		ask[i] = {l,r,i};
	}
	unit = sqrt(n);
	sort(ask+1,ask+m+1,cmp);
	
	int L = 1,R = 0;
	LL ans = 0;
	for(int i=1;i<=m;i++){
		int l = ask[i].l;
		int r = ask[i].r;
		while(L < l){
			ans -= getnum(L);
			add(apos[L].pos,-1);
			L++;
		}
		while(L > l){
			L--;
			add(apos[L].pos,1);
			ans += getnum(L);
		}
		while(R < r){
			R++;
			add(apos[R].pos,1);
			ans += getnum(R);
		}
		while(R > r){
			ans -= getnum(R);
			add(apos[R].pos,-1);
			R--;
		}
		ac[ask[i].id] = ans;
	}
	for(int i=1;i<=m;i++){
		cout << ac[i] << "\n";
	}
	
	
	
	return 0;
}
Prev
2021-05-06 14:16:00 # ACM
Next