首页 > 代码库 > BZOJ1878 SDOI2009 HH的项链 树状数组
BZOJ1878 SDOI2009 HH的项链 树状数组
题意：给定一个颜色序列，每组询问给出区间[l,r]，求[l,r]中不同颜色的数量
题解：
首先把所有颜色离散化，然后离线，将询问按右区间升序排列。从1-N把整个序列扫一遍，设Pos[i]为第i个颜色最后出现的位置，假定当前扫到的位置为i，则更新Pos[a[i]]，那么问题变成了：求一个序列（Pos）中，大于等于一个数（L）的数的数量。
用树状数组维护Pos=j的数的数量，每次查询树状数组中L-N的和即可。
貌似SDOI不喜欢考大型数据结构啊……坐等今年打脸
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <map>using namespace std;#define lowbit(x) (x&(-x))const int MAXN=50000+2;const int MAXM=200000+2;struct Hash{ int u,t; Hash *Next; Hash(){} Hash(int _u,int _t,Hash *_Next):u(_u),t(_t),Next(_Next){}}*Tab[MAXN],mem[MAXM];int N,M,a[MAXN],cnt,Ans[MAXM],Pos[MAXN],s[MAXN];map<int,int> m;void Update(int p,int x){ while(p<=N) s[p]+=x,p+=lowbit(p);}int Sum(int p){ int Ret=0; while(p) Ret+=s[p],p-=lowbit(p); return Ret;}int main(){ scanf("%d",&N); for(int i=1;i<=N;i++){ scanf("%d",a+i); if(!m[a[i]]) m[a[i]]=++cnt; a[i]=m[a[i]]; } scanf("%d",&M),cnt=0; for(int i=1,l,r;i<=M;i++){ scanf("%d %d",&l,&r); mem[cnt].u=l,mem[cnt].t=i,mem[cnt].Next=Tab[r],Tab[r]=&mem[cnt],cnt++; } for(int i=1;i<=N;i++){ if(Pos[a[i]]) Update(Pos[a[i]],-1); Pos[a[i]]=i,Update(i,1); for(Hash *p=Tab[i];p;p=p->Next) Ans[p->t]=Sum(N)-Sum(p->u-1); } for(int i=1;i<=M;i++) printf("%d\n",Ans[i]); return 0;}
BZOJ1878 SDOI2009 HH的项链 树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。