好贷网好贷款

UVALive - 5902 Movie collection

发布时间:2016-12-4 12:00:08 编辑: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

相关文章

相关评论