1878: [SDOI2009]HH的项链(离线+树状数组)-布布扣-bubuko.com

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 8511 Solved: 4099
[Submit][Status][Discuss]

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一

段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一

个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只

好求助睿智的你，来解决这个问题。

Input

第一行：一个整数N，表示项链的长度。

第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。

第三行：一个整数M，表示HH询问的个数。

接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

N ≤ 50000，M ≤ 200000。

Output

M行，每行一个整数，依次表示询问对应的答案。

Sample Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

Sample Output

2
2
4

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <iomanip>
 6 #include <sstream>
 7 #include <vector>
 8 #include <map>
 9 using namespace std;
10 const int maxn=5*1e4+5;
11 const int maxm=2*1e5+2;
12 map<int,int> ma;
13 int cnt[maxn],arr[maxn],ans[maxm];
14 int n,x,y,m;
15 struct Node{ int x,y,id; }A[maxm];
16 bool cmp(Node a,Node b){ return a.y<b.y; }  //按照右边的进行排序
17 
18 int lowbits(int x) { return x&-x; }
19 void updata(int x,int value){
20     while(x<=maxn){   //树状数组下标不能从0开始
21         cnt[x]+=value;
22         x+=lowbits(x);
23     }
24 }
25 int query(int x){    //x是下标的位置
26     int res=0;
27     while(x>0){
28         res+=cnt[x];
29         x-=lowbits(x);
30     }
31     return res;
32 }
33 
34 int main(){
35     scanf("%d",&n);
36     for(int i=1;i<=n;i++)  scanf("%d",&arr[i]);
37     scanf("%d",&m);
38     for(int i=1;i<=m;i++)  scanf("%d%d",&A[i].x,&A[i].y),A[i].id=i;    //离线
39     sort(A+1,A+1+m,cmp);
40     int L=1;
41     for(int i=1;i<=m;i++){
42         for(int j=L;j<=A[i].y;j++){
43             if(ma[arr[j]]!=0) updata(ma[arr[j]],-1);   //如果前面有过消除前面的影响
44             updata(j,1);   //更新
45             ma[arr[j]]=j;   //更改下标的位置
46         }
47         L=A[i].y+1;
48         ans[A[i].id]=query(A[i].y)-query(A[i].x-1);
49     }
50     for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
51     return 0;
52 }

View Code

1878: [SDOI2009]HH的项链(离线+树状数组)

原文：https://www.cnblogs.com/qq-1585047819/p/11409475.html