洛谷 P1972 [SDOI2009]HH的项链

题目传送门

解题思路:

1.按每个要求的区间的右端点排序一下

2.树状数组tree[j]维护从1到j区间内不同数字的个数有多少个

3.然后用前缀和的思想就好（tree[r]-tree[l-1]）

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #define maxn 1000002 
 5 #define next nex
 6 #define lowbit(x) x & -x
 7 
 8 using namespace std;
 9 
10 int num[maxn],tree[maxn],b[maxn],ans[maxn],n,m;
11 //b[i]表示i出现的最靠右的位置
12 struct kkk {
13     int l,r;
14     int pos;
15 }e[maxn];
16 
17 bool cmp(kkk a,kkk b) {
18     return a.r < b.r;
19 }
20 
21 inline void add(int x,int v) {
22     while(x <= n) {
23         tree[x] += v;
24         x += lowbit(x);
25     }
26 }
27 
28 inline int query(int x) {
29     int ans = 0;
30     while(x > 0) {
31         ans += tree[x];
32         x -= lowbit(x);
33     }
34     return ans;
35 }
36 
37 int main()
38 {
39     scanf("%d",&n);
40     for(int i = 1;i <= n; i++)
41         scanf("%d",&num[i]);
42     scanf("%d",&m);
43     for(int i = 1;i <= m; i++) {
44         scanf("%d%d",&e[i].l,&e[i].r);
45         e[i].pos = i;
46     }
47     sort(e + 1,e + m + 1,cmp);
48     int next = 1;
49     for(int i = 1;i <= m; i++) {
50         for(int j = next;j <= e[i].r; j++) {
51             if(b[num[j]])
52                 add(b[num[j]],-1);//之前有过这个点,减去1 
53             add(j,1);
54             b[num[j]] = j;
55         }
56         next = e[i].r - 1;
57         ans[e[i].pos] = query(e[i].r) - query(e[i].l - 1);
58     }
59     for(int i = 1;i <= m; i++)
60         printf("%d
",ans[i]);
61     return 0;
62 }