【树状数组】SPOJ D-query
2021-05-07 13:57:00 # ACM

——-

题链

对于每一个$a[i]$可以记录它上一次出现的位置；

$1.$可以用树状数组解（离线）：对询问排序（询问的$r$从小到大），右指针移动则$add(R,1)$，然后对$a[R]$上一次出现的位置$add(pos,-1)$，对于一个询问则是$query(r)-query(l-1)$；

$2.$可以主席树记录原数组下标方式解（在线）：对于新加入的$a[i]$，在$i$这个位置$+1$，在$a[i]$上一次出现的位置$-1$，对于主席树的每一棵树$p[root]$就是$[1,r]$的种类数，对于每一个询问$[l,r]$，就是先得知插入$r$的版本号$root$，在这一棵树上求$[l,r]$的权值和；

$3.$可以主席树记录权值（在线）：对于每一个元素$a[i]$，记录这个元素下一次出现的位置$aft[i]$，对$aft[i]$建立主席树，此时问题就变成在$[l,r]$范围内查找大于$r$的数字个数。对于新加入的一个$aft[i]$，新建树链在$aft[i]$这个权值点$++$，询问就是普通主席树询问方式；

方式一

$1.$可以用树状数组解（离线）：对询问排序（询问的$r$从小到大），右指针移动则$add(R,1)$，然后对$a[R]$上一次出现的位置$add(pos,-1)$，对于一个询问则是$query(r)-query(l-1)$；

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
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
//#pragma GCC optimize("O2")
using namespace std;
using namespace __gnu_pbds;
#define Pair pair<LL,LL>
#define Combine Pair, greater<Pair>, pairing_heap_tag
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e18
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-9
#define mod 99999997

LL n,m;
struct node{
	LL pos,l,r;
}cp[MS];
LL ac[MS];
LL a[MS];
LL p[MS];
LL lapos[MS]; 

inline LL read() {
	LL x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}

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

bool cmp(node a,node b){
	if(a.r == b.r) return a.l < b.l;
	return a.r < b.r;
}

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

LL get_sum(LL pos){
	LL ans = 0;
	for(;pos;pos-=lowbit(pos)) ans += p[pos];
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	n = read();
	for(int i=1;i<=n;i++) a[i] = read();
	m = read();
	for(int i=1;i<=m;i++){
		cp[i].l = read();
		cp[i].r = read();
		cp[i].pos = i;
	}
	sort(cp+1,cp+m+1,cmp);
	LL apos = 1;
	for(int i=1;i<=m;i++){
		for(;apos<=cp[i].r;apos++){
			if(lapos[a[apos]])
				add(lapos[a[apos]],-1);
			add(apos,1);
			lapos[a[apos]] = apos;
		}
		ac[cp[i].pos] = get_sum(cp[i].r) - get_sum(cp[i].l-1);
	}
	for(int i=1;i<=m;i++){
		cout << ac[i] << "\n";
	}


	return 0;

}

方式二

$2.$可以主席树记录原数组下标方式解（在线）：对于新加入的$a[i]$，在$i$这个位置$+1$，在$a[i]$上一次出现的位置$-1$，对于主席树的每一棵树$p[root]$就是$[1,r]$的种类数，对于每一个询问$[l,r]$，就是先得知插入$r$的版本号$root$，在这一棵树上求$[l,r]$的权值和；

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
#include <bits/stdc++.h>
using namespace std;
#define MS 1000009
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define ll long long
#define MAXN 20000000000
#define mod 1000000007

int n,m,k;
struct node{
	int l,r,val;
}p[MS<<5];
int a[MS];
int pre[MS];
int rtpos[MS*2];
int tot;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}

int build(int l,int r){
	int rt = ++tot;
	if(l == r) return rt;
	int m = l+r>>1;
	p[rt].l = build(l,m);
	p[rt].r = build(m+1,r);
	return rt;
}

void push_up(int rt){
	p[rt].val = p[p[rt].l].val + p[p[rt].r].val;
} 

int update(int lart,int pos,int l,int r,int val){
	int rt = ++tot;
	p[rt] = p[lart];
	if(l == r){
		p[rt].val += val;
		return rt;
	}
	int m = l+r>>1;
	if(m >= pos) p[rt].l = update(p[lart].l,pos,l,m,val);
	else p[rt].r = update(p[lart].r,pos,m+1,r,val);
	push_up(rt);
	return rt;
}

int query(int rt,int L,int R,int l,int r){
	if(L <= l && r <= R) return p[rt].val;
	int ans = 0;
	int m = l+r>>1;
	if(m >= L) ans += query(p[rt].l,L,R,l,m);
	if(m <  R) ans += query(p[rt].r,L,R,m+1,r);
	return ans;
}

int main() {
	//ios::sync_with_stdio(false);
	n = read();
	for(int i=1;i<=n;i++){
		a[i] = read(); 
	}
	rtpos[0] = build(1,n);
	for(int i=1;i<=n;i++){
		if(pre[a[i]] == 0){
			rtpos[i] = update(rtpos[i-1],i,1,n,1);
		} 
		else{
			int tmp = update(rtpos[i-1],pre[a[i]],1,n,-1);
			rtpos[i] = update(tmp,i,1,n,1);
		}
		pre[a[i]] = i;
	}
	m = read();
	while(m--){
		int l,r;
		l = read();
		r = read();
		printf("%d\n",query(rtpos[r],l,r,1,n));
		//cout << query(rtpos[r],l,r,1,n) << "\n";
	}
	
	
	return 0;
}

方式三

$3.$可以主席树记录权值（在线）：对于每一个元素$a[i]$，记录这个元素下一次出现的位置$aft[i]$，对$aft[i]$建立主席树，此时问题就变成在$[l,r]$范围内查找大于$r$的数字个数。对于新加入的一个$aft[i]$，新建树链在$aft[i]$这个权值点$++$，询问就是普通主席树询问方式；

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
#include <iostream>
#include <algorithm>
using namespace std;
#define MS 1000009
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define ll long long
#define MAXN 20000000000
#define mod 1000000007

int n,m,k;
struct node{
	int l,r,val;
}p[MS<<5];
int a[MS];
int aft[MS];
int pre[MS];
int rtpos[MS];
int tot;

int build(int l,int r){
	int rt = ++tot;
	if(l == r) return rt;
	int m = l+r>>1;
	p[rt].l = build(l,m);
	p[rt].r = build(m+1,r);
	return rt;
}

void push_up(int rt){
	p[rt].val = p[p[rt].l].val + p[p[rt].r].val;
}

int update(int lart,int l,int r,int pos){
	int rt = ++tot;
	p[rt] = p[lart];
	if(l == r){
		p[rt].val++;
		return rt;
	}
	int m = l+r>>1;
	if(pos <= m) p[rt].l = update(p[lart].l,l,m,pos);
	else p[rt].r = update(p[lart].r,m+1,r,pos);
	push_up(rt);
	return rt;
}

int query(int L,int R,int l,int r,int tar){
	if(l == r) return p[R].val-p[L].val;
	int ans = 0;
	int m = l+r>>1;
	if(tar <= m){
		int x = p[p[R].r].val - p[p[L].r].val;
		ans += x + query(p[L].l,p[R].l,l,m,tar);
	} 
	else{
		ans += query(p[L].r,p[R].r,m+1,r,tar);
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		if(pre[a[i]]) aft[pre[a[i]]] = i;
		pre[a[i]] = i;
	}
	for(int i=1;i<=n;i++){
		if(!aft[i]) aft[i] = n+1;
	}
	
	rtpos[0] = build(1,n+1);
	for(int i=1;i<=n;i++){
		rtpos[i] = update(rtpos[i-1],1,n+1,aft[i]);
	}
	
	cin >> m;
	while(m--){
		int l,r;
		cin >> l >> r;
		cout << query(rtpos[l-1],rtpos[r],1,n+1,r+1) << "\n";
	}
	
	return 0;
}
Prev
2021-05-07 13:57:00 # ACM
Next