【树状数组维护区间种类数】洛谷 P1972 HH的项链
2021-03-25 15:54:00 # ACM

题链

询问区间种类不能直接通过类似 $get_sum(r)-get_sum(l-1)$ 的方式去得出答案

如何使得上述方式可以求解成为关键，可以将$m$个询问按照右区间$r$从小到大排列，不试图将所有数据（题给的一串贝壳数组）一起建立树状数组，通过一个个将数组中的元素加入树状数组时，对于该种类上一次出现的位置$lastpos$可以去掉，这一次出现时记录现在位置，由于对$m$个询问排序离线操作，就可通过 $get_sum(r)-get_sum(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;

}
Prev
2021-03-25 15:54:00 # ACM
Next