首页 > 代码库 > bzoj1878--离线+树状数组
bzoj1878--离线+树状数组
这题在线做很麻烦，所以我们选择离线。
首先预处理出数组next[i]表示i这个位置的颜色下一次出现的位置。
然后对与每种颜色第一次出现的位置x,将a[x]++。
将每个询问按左端点排序，再从左往右扫，将next[i]++，如果是询问就先返回sum[r]-sum[l-1](sum是a的前缀和)。其中前缀和可以用树状数组维护。
因为做一个询问之前l到r的所有颜色都加且仅加了1，所以答案就是sum[r]-sum[l-1]。
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,100000,stdin); if(p1==p2)return EOF; } return *p1++;}inline void read(int& x){ char c=nc(),b=1; for(;!(c>=‘0‘&&c<=‘9‘);c=nc())if(c==‘-‘)b=-1; for(;c>=‘0‘&&c<=‘9‘;x=x*10+c-48,c=nc());x*=b;}struct ask{ int s,e,f;}b[200001];inline bool cmp(ask x,ask y){ return x.s<y.s;}int ans[200001],i,j,k=1,n,a[50001],last[1000001],m,c[50001],x,y,next[50001];inline int lowbit(int x){ return x&(-x);}inline void update(int x){ for(int i=x;i<=n;i+=lowbit(i))c[i]++;}inline int query(int x){ int ans=0; for(int i=x;i>0;i-=lowbit(i))ans+=c[i]; return ans;}int main(){ read(n); for(i=1;i<=n;i++)read(a[i]); read(m); for(i=1;i<=m;i++)read(b[i].s),read(b[i].e),b[i].f=i; sort(b+1,b+m+1,cmp); for(i=1;i<=n;i++) if(!last[a[i]]){ last[a[i]]=i; update(i); }else{ next[last[a[i]]]=i; last[a[i]]=i; } for(i=1;i<=m;i++){ while(k<b[i].s){ if(next[k])update(next[k]); k++; } ans[b[i].f]=query(b[i].e)-query(b[i].s-1); } for(i=1;i<=m;i++)printf("%d\n",ans[i]); return 0;}
bzoj1878--离线+树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。