UVALive - 5902 Movie collection

发布时间:2014-10-22 19:55:09编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVALive - 5902 Movie collection",主要涉及到UVALive - 5902 Movie collection方面的内容,对于UVALive - 5902 Movie collection感兴趣的同学可以参考一下。

题意:1~n按从上到下排列,m次询问,每次问x之前的有多少个数字,并且将x放到队首 思路:树状数组,首先将1~n下标向后移m位,每次询问后都将一个数字移到队首,每次 都更新了节点的大小,并且问到了前缀和,所以用树状数组 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 201010; int pos[MAXN],c[MAXN]; int n,m; void Update(int x,int d){ while (x <= n+m+1) c[x] += d,x += x&-x; } int sum(int x){ int ret = 0; while (x > 0) ret += c[x],x -= x&-x; return ret; } int main(){ int t; scanf("%d",&t); while (t--){ scanf("%d%d",&n,&m); memset(pos,0,sizeof(pos)); memset(c,0,sizeof(c)); for (int i = 1; i <= n; i++){ pos[i] = i+m; Update(pos[i],1); } for (int i = 1; i <= m; i++){ int x; scanf("%d",&x); int ans = sum(pos[x]-1); Update(pos[x],-1); Update(m-i+1,1); pos[x] = m-i+1; if (i != m) printf("%d ",ans); else printf("%d\n",ans); } } return 0; }


上一篇:《30天自制操作系统》学习笔记——第十一天
下一篇:在 Yarn 上 安装 Spark 0.9.0

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款