牛客练习赛52.Galahad（树状数组维护区间不相同数的和）

链接：/acm/contest/1084/B

来源：牛客网

Galahad

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 131072K，其他语言262144K

64bit IO Format: %lld

题目描述

本题推荐BGM：Galahad and Scientific Witchery

魔女要测试骑士的能力，要求他维护一个长度为 的序列，每次要询问一个区间的和。

但是魔女觉得太简单了，骑士能轻松记住 个数作为前缀和。

于是，魔女要求他回答一个区间的和，但如果某一个数在这个区间出现了多次，这个数只能被计算一次。

输入描述:

第一行两个整数 ，表示数列长度和询问个数。第二行 个整数，第i个整数为ai(1≤ai≤500000)a_i(1\le a_i\le500\ 000)ai​(1≤ai​≤500000)，表示序列中的第i项。接下来 行，每行两个整数 ，表示询问的区间。

输出描述:

输出 行，每行一个整数表示这次询问的答案。

示例1

输入

复制

5 31 3 3 2 11 51 32 4

输出

复制

645

注意到这样一个事实：如果我当前询问的区间右端点为r，左端点为l，那么在这个区间内，所有元素，我都只需要保存它最后一次出现的位置就可以了。所以可以先离线询问，然后对每个询问的右端点排序，用树状数组维护区间和，从第一个元素开始，如果遇到之前出现过的元素，就将之前的元素删除，并把现在这个元素加入树状数组中，如果当前元素为区间右端点时，直接求和得到答案。

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=5e5+10;struct Query{int l,r,id;}Q[maxn];ll s[maxn];int pos[maxn];int n,m;int a[maxn];ll ans[maxn];int lowbit(int x){return x&-x;}void add(int x,int d){while(x<=n){s[x]+=d;x+=lowbit(x);}}ll sum(int x){ll res=0;while(x){res+=s[x];x-=lowbit(x);}return res;}int cmp(const Query a,const Query b){return a.r<b.r||(a.r==b.r&&a.l<b.l);}signed main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=m;i++){scanf("%d%d",&Q[i].l,&Q[i].r);Q[i].id=i;}sort(Q+1,Q+m+1,cmp);for(int i=1;i<=n;i++)s[i]=0;int i=1;int now=1;while(i<=n){while(now<=Q[i].r){if(pos[a[now]]!=0){add(pos[a[now]],-a[now]);//删除之前出现过的数add(now,a[now]);pos[a[now]]=now;}else{pos[a[now]]=now;add(now,a[now]);}if(now==Q[i].r){ans[Q[i].id]=sum(Q[i].r)-sum(Q[i].l-1);break;}now++;}i++;}for(i=1;i<=m;i++){printf("%lld\n",ans[i]);}return 0;}

如果觉得《牛客练习赛52.Galahad（树状数组维护区间不相同数的和）》对你有帮助，请点赞、收藏，并留下你的观点哦！