【题目】
查询区间和，如果区间元素重复出现则计数一次。
【题解】
按区间的右端点建立树状数组，维护区间[1,R]的每个元素的最右位置。按查询区间的右端点排序，依次处理，每次更新当前值的最右位置即可。
若要查询区间不同元素个数，把
for(;it<=q[i].R;it++){if(vis[a[it]]) //这个数之前出现过add(vis[a[it]],-a[it]); //取消标记vis[a[it]]=it; //记录最大位置add(it,a[it]); //添加新标记}
改为如下代码即可
for(;it<=q[i].R;it++){if(vis[a[it]]) //这个数之前出现过add(vis[a[it]],-1); //取消标记vis[a[it]]=it; //记录最大位置add(it,1); //添加新标记}
【代码】
#include<bits/stdc++.h>using namespace std;const int maxn=5e5+10;typedef long long ll;struct p{int L,R,num;}q[maxn];int cmp(p a,p b){return a.R<b.R;}ll sum[maxn]={0},ans[maxn]={0};int n,vis[maxn]={0};ll a[maxn];void add(int p,ll y){while(p<=n){sum[p]+=y;p+=(p&-p);}}ll cx(int p){ll ans=0;while(p){ans+=sum[p];p-=(p&-p);}return ans;}int main(){int m; scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=m;i++){scanf("%d%d",&q[i].L,&q[i].R);q[i].num=i;}sort(q+1,q+1+m,cmp);int it=1;for(int i=1;i<=m;i++){for(;it<=q[i].R;it++){if(vis[a[it]]) //这个数之前出现过add(vis[a[it]],-a[it]); //取消标记vis[a[it]]=it; //记录最大位置add(it,a[it]); //添加新标记}it=q[i].R+1;ans[q[i].num]=cx(q[i].R)-cx(q[i].L-1); //查询}for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0;}
如果觉得《牛客练习赛52 B：Galahad（树状数组维护区间不同元素和(个数)）》对你有帮助，请点赞、收藏，并留下你的观点哦！
