Movie collection （树状数组）

Movie collection （树状数组）

Mr. K. I. has a very big movie collection. He has organized his collection in a big stack. Whenever hewants to watch one of the movies, he locates the movie in this stack and removes it carefully, ensuringthat the stack doesn’t fall over. After he finishes watching the movie, he places it at the top of thestack.Since the stack of movies is so big, he needs to keep track of the position of each movie. It issufficient to know for each movie how many movies are placed above it, since, with this information,its position in the stack can be calculated. Each movie is identified by a number printed on the moviebox.Your task is to implement a program which will keep track of the position of each movie. Inparticular, each time Mr. K. I. removes a movie box from the stack, your program should print thenumber of movies that were placed above it before it was removed.InputOn the first line a positive integer: the number of test cases, at most 100. After that per test case:• one line with two integers n and m (1 ≤ n, m ≤ 100000): the number of movies in the stack andthe number of locate requests.• one line with m integers a1, . . . , am (1 ≤ ai ≤ n) representing the identification numbers of moviesthat Mr. K. I. wants to watch.For simplicity, assume the initial stack contains the movies with identification numbers 1, 2, . . . , nin increasing order, where the movie box with label 1 is the top-most box.OutputPer test case:• one line with m integers, where the i-th integer gives the number of movie boxes above the boxwith label ai, immediately before this box is removed from the stack.Note that after each locate request ai, the movie box with label aiis placed at the top of the stack.Sample Input23 33 1 15 34 4 5Sample Output2 1 03 0 4

题目大概：

给出t个样例，每个有n个数叠起来放着（1在最上面），m条询问，每条询问，查看这个数的上面有多少个数，并且把这个数放在最上面。

思路：

一看题目的意思，感觉很有树状数组的性质，删除就是把这个点的位置赋值为-1，插入直接赋值为1。但是仔细思考一下，感觉不太好做，因为点是插在前面的。所以。我们可以把数倒着插入。这样最后的位置信息就是反的，需要用n减去算出来的数。

代码：

#include using namespace std;//const int maxn=1e5+10;int c[maxn<<1];int N,n;int lowbit(int x){ return x&(-x);}void add(int x,int v){ while(x<=(maxn<<1)-5) { c[x]+=v; x+=lowbit(x); }}int sum(int x){ int sum=0; while(x>0) { sum+=c[x]; x-=lowbit(x); } return sum;}int b[maxn<<1],d[maxn<<1];int main(){ int ans; int t; int m; scanf("%d",&t); while(t--) { scanf("%d%d",&N,&m); ans=0; n=N; memset(d,0,sizeof(d)); memset(c,0,sizeof(c)); int u; for(int i=1;i<=N;i++) //倒着把数插入 { b[i]=N-i+1; add(b[i],1); } for(int i=1;i<=m;i++) { scanf("%d",&u); d[ans++]=n-sum(b[u]); add(b[u],-1); //删除 b[u]=++N; add(b[u],1); //插入 } printf("%d",d[0]); for(int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。