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

【题目】

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

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

【题解】

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

AC代码：

 #include<bits/stdc++.h>

 using namespace std;
 #define int long long
 #define lowbit(x) (x&(-x))
 #define N 500009
 int n,m;
 int arr[N];
 int ans[N];
 int mp[N];
 struct str{
     int l,r,id;
 }st[N];
 int c[N];
 inline void update(int x,int v){
     for(int i=x;i<=n;i+=lowbit(i))
         c[i]+=v;
 }
 inline int getsum(int x){
     int res=;
     for(int i=x;i;i-=lowbit(i))
         res+=c[i];
     return res;
 }
 bool cmp(str a,str b){
     return a.r<b.r;
 }
 signed main(){
     cin>>n>>m;
     memset(mp,,sizeof(mp));

     for(int i=;i<=n;i++){
         scanf("%lld",&arr[i]);
     }
     for(int i=;i<=m;i++){
         scanf("%lld%lld",&st[i].l,&st[i].r);
         st[i].id=i;
     }
     sort(st+,st++m,cmp);
     int now=;
     for(int i=;i<=m;i++){
         for(int j=now;j<=st[i].r;j++){
             if(mp[arr[j]]){
                 update(mp[arr[j]],-arr[j]);
             }

             update(j,arr[j]);
             mp[arr[j]]=j;
         }
         now=st[i].r+;
         ans[st[i].id]=getsum(st[i].r)-getsum(st[i].l-);
     }
     for(int i=;i<=m;i++){
         printf("%lld\n",ans[i]);
     }
     return ;
 }

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

 #include<bits/stdc++.h>

 using namespace std;
 #define int long long
 #define lowbit(x) (x&(-x))
 #define N 500009
 int n,m;
 int arr[N];
 int ans[N];
 int mp[N];
 struct str{
     int l,r,id;
 }st[N];
 int c[N];
 inline void update(int x,int v){
     for(int i=x;i<=n;i+=lowbit(i))
         c[i]+=v;
 }
 inline int getsum(int x){
     int res=;
     for(int i=x;i;i-=lowbit(i))
         res+=c[i];
     return res;
 }
 bool cmp(str a,str b){
     return a.r<b.r;
 }
 signed main(){
     cin>>n>>m;
     memset(mp,,sizeof(mp));

     for(int i=;i<=n;i++){
         scanf("%lld",&arr[i]);
     }
     for(int i=;i<=m;i++){
         scanf("%lld%lld",&st[i].l,&st[i].r);
         st[i].id=i;
     }
     sort(st+,st++m,cmp);
     int now=;
     for(int i=;i<=m;i++){
         for(int j=now;j<=st[i].r;j++){
             if(mp[arr[j]]){
 update(mp[arr[j]],-);
             }

             update(j,);
             mp[arr[j]]=j;
         }
         now=st[i].r+;
         ans[st[i].id]=getsum(st[i].r)-getsum(st[i].l-);
     }
     for(int i=;i<=m;i++){
         printf("%lld\n",ans[i]);
     }
     return ;
 }