牛客练习赛52 B题【树状数组维护区间和{查询区间和，如果区间元素重复出现则计数一次}】补题ing

【题目】

查询区间和，如果区间元素重复出现则计数一次。

链接：https://ac.nowcoder.com/acm/contest/1084/B

【题解】

　　将询问按r排序，维护每个数最后出现的位置，并用树状数组维护前缀和即可

AC代码：

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define int long long
 5 #define lowbit(x) (x&(-x))
 6 #define N 500009
 7 int n,m;
 8 int arr[N];
 9 int ans[N];
10 int mp[N];
11 struct str{
12     int l,r,id;
13 }st[N];
14 int c[N];
15 inline void update(int x,int v){
16     for(int i=x;i<=n;i+=lowbit(i))  
17         c[i]+=v;
18 }
19 inline int getsum(int x){
20     int res=0; 
21     for(int i=x;i;i-=lowbit(i))
22         res+=c[i]; 
23     return res;
24 }
25 bool cmp(str a,str b){
26     return a.r<b.r;
27 }
28 signed main(){
29     cin>>n>>m;
30     memset(mp,0,sizeof(mp));
31     
32     for(int i=1;i<=n;i++){
33         scanf("%lld",&arr[i]);
34     }
35     for(int i=1;i<=m;i++){
36         scanf("%lld%lld",&st[i].l,&st[i].r);
37         st[i].id=i;
38     }
39     sort(st+1,st+1+m,cmp);
40     int now=1;
41     for(int i=1;i<=m;i++){
42         for(int j=now;j<=st[i].r;j++){
43             if(mp[arr[j]]){
44                 update(mp[arr[j]],-arr[j]);
45             }
46             
47             update(j,arr[j]);
48             mp[arr[j]]=j;
49         }
50         now=st[i].r+1;
51         ans[st[i].id]=getsum(st[i].r)-getsum(st[i].l-1);
52     }
53     for(int i=1;i<=m;i++){
54         printf("%lld
",ans[i]);
55     }
56     return 0;
57 }

如果要查询区间不同元素个数：则将代码改为：

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define int long long
 5 #define lowbit(x) (x&(-x))
 6 #define N 500009
 7 int n,m;
 8 int arr[N];
 9 int ans[N];
10 int mp[N];
11 struct str{
12     int l,r,id;
13 }st[N];
14 int c[N];
15 inline void update(int x,int v){
16     for(int i=x;i<=n;i+=lowbit(i))  
17         c[i]+=v;
18 }
19 inline int getsum(int x){
20     int res=0; 
21     for(int i=x;i;i-=lowbit(i))
22         res+=c[i]; 
23     return res;
24 }
25 bool cmp(str a,str b){
26     return a.r<b.r;
27 }
28 signed main(){
29     cin>>n>>m;
30     memset(mp,0,sizeof(mp));
31     
32     for(int i=1;i<=n;i++){
33         scanf("%lld",&arr[i]);
34     }
35     for(int i=1;i<=m;i++){
36         scanf("%lld%lld",&st[i].l,&st[i].r);
37         st[i].id=i;
38     }
39     sort(st+1,st+1+m,cmp);
40     int now=1;
41     for(int i=1;i<=m;i++){
42         for(int j=now;j<=st[i].r;j++){
43             if(mp[arr[j]]){
44                 update(mp[arr[j]],-1);
45             }
46             
47             update(j,1);
48             mp[arr[j]]=j;
49         }
50         now=st[i].r+1;
51         ans[st[i].id]=getsum(st[i].r)-getsum(st[i].l-1);
52     }
53     for(int i=1;i<=m;i++){
54         printf("%lld
",ans[i]);
55     }
56     return 0;
57 }