UVALive-5902: Movie collection

树状数组

Description

Mr. K. I. has a very big movie collection. He has organized his collection in a big stack. Whenever he wants to watch one of the movies, he locates the movie in this stack and removes it carefully, ensuring that the stack doesn’t fall over. After he finishes watching the movie, he places it at the top of the stack.

Since the stack of movies is so big, he needs to keep track of the position of each movie. It is sufficient 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 movie
box.

Your task is to implement a program which will keep track of the position of each movie. In particular, each time Mr. K. I. removes a movie box from the stack, your program should print the number of movies that were placed above it before it was removed.

Input

On 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 and
the number of locate requests.
• one line with m integers a1, . . . , am (1 ≤ ai ≤ n) representing the identification numbers of movies that Mr. K. I. wants to watch.

For simplicity, assume the initial stack contains the movies with identification numbers 1, 2, . . . , n in increasing order, where the movie box with label 1 is the top-most box.

Output

Per test case:
• one line with m integers, where the i-th integer gives the number of movie boxes above the box with label ai , immediately before this box is removed from the stack.

Note that after each locate request ai , the movie box with label ai is placed at the top of the stack.

Sample Input

2
3 3
3 1 1
5 3
4 4 5

Sample Output

2 1 0
3 0 4

题意：有t组数据，每组数据，先输入n和m，表示有n个电影放在一摞，从上到下编号分别为1到n，接下来m次询问，每次问编号为x的电影，它的上面放了多少个电影，然后将它抽出来，放在最顶上。

分析： n和m都在1e5之内，开一个大小为2e5的数组，将电影从1e5+1开始放，那么就是说，第1个电影放在1e5+1，第2个放在1e5+2……以此类推，用树状数组将这些位置置1。位置改变就更新树状数组的相应位置的值。求每个数前面有多少个1就行。

• 代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m;
int a[2*maxn],pos[maxn];
int sum[2*maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y)
{
    for(int i=x;i<=n+maxn;i+=lowbit(i))
        sum[i]+=y;
}
int query(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans+=sum[i];
    return ans;
}
int main()
{
    int t,x;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(sum,0,sizeof(sum));
        for(int i=1e5+1,j=1;i<=n+1e5;i++,j++)
        {
            add(i,1); //相应位置置1
            pos[j]=i; //存每个数所在位置
        }
        int p=1e5+1; //指在最顶层
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            if(i!=1) printf(" ");
            printf("%d",query(pos[x])-1); //查询该数前1的个数
            p--; //顶层位置改变
            add(pos[x],-1); //更新树状数组
            pos[x]=p; //更新该数的位置
            add(p,1);
        }
        printf("\n");
    }
    return 0;
}