P1972 [SDOI2009] HH的项链

本质上是区间查询$[l,r]$不重复元素的个数.
考虑离线处理,按$r$升序排序区间.假设当前区间为$[l,r]$,我们希望查询中的$query(r)-query(l-1)$直接就是答案。考虑上一个查询的区间是$[pr{e}_l,pr{e}_r]$.区间$[pr{e}_r+1,r]$是需要我们新插入的部分,如果我们能保证该区间插入不会破坏数据结构每个元素唯一性就成功了
考虑用树状数组维护这个东西,在$[pr{e}_r+1,r]$插入时,使用一个$pos[i]$维护某个数字是否出现过,若出现过,当前最右边是多少.
因为我们回答查询的顺序是按$r$升序的,所以对于两个重复元素的位置$i,j$
如果$i<j$,显然我们可以用$j替换掉i$的贡献.
所以我们记录这个数字上一次出现的位置$pos[i]$,如果出现重复的贡献了,就$add(pos[a[i]],-1)$,再$add(i,1)$
总结:利用查询是离线的特点,可以把查询区间排序,然后利用区间重复元素不用重复计算的特点,让每个位置都只被插入/删除一次.
代码：

/*
Stairs upon the temple
I climb and I crawl in
People travel millions of miles just to see it
But they never conquer this way
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
int tree[maxn];int pos[maxn];
int n;
void add(int x,int w){
	for(int i=x;i<=n;i+=(i&(-i))){
		tree[i] +=w; 
	}
}
int query(int x){
	int res = 0;
	while(x){
		res+=tree[x];
		x-=(x&(-x));
	}
	return res;
}
int query(int l,int r){
	return query(r)-query(l-1);
}
int a[maxn];int ans[maxn];
struct Node{
	int l,r,id;
	bool operator < (const Node&rhs)const{
		if(r==rhs.r) return l<rhs.l;
		return r<rhs.r;
	}
};
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int m;cin>>m;
	vector<Node> ask(m+1);
	for(int i=1;i<=m;i++){
		cin>>ask[i].l>>ask[i].r;
		ask[i].id = i;
	}
	sort(ask.begin()+1,ask.end());
	int pre_r = 1;
	for(int i=1;i<=m;i++){
		for(int j=pre_r;j<=ask[i].r;j++){
			if(pos[a[j]]) add(pos[a[j]],-1);
			add(j,1);pos[a[j]] = j;
		}
		pre_r = ask[i].r+1;
		ans[ask[i].id] = query(ask[i].l,ask[i].r);
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
}
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