树状数组-UVA1513--Movie collection

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 (1n,m100000): the number of movies in the stack and the number of locate requests.
one line with m integers a1,..., am(1ain) representing the identification numbers of movies that Mr. K. I. wants to watch.
For simplicity, assume the initial stack contains the movies with identification numbers1, 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 labelai, immediately before this box is removed from the stack.
Note that after each locate request ai, the movie box with labelai 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

题意：有n部电影，询问m次，询问第i部电影前面有多少部电影。每次询问把询问的电影放到栈的顶部，以第一组为例：询问3,3前面有1和2两部电影，就输出2；询问1，因为3调到第一位了，1前面就有1部电影，就输出1；询问1，1已经调到第一位了1前面没有电影，就输出0.

思路：树状数组，开两个数组，用一个数组存电影在放入另一个数组中的下标位置，另一个数组用于树状数组使用，其中默认加的每一项的值都是1；每取一部电影，就将当前这部电影所在位置的值归为0，即在这个位置更新树状数组，用add做减1操作；之后将这部电影放在新的未使用的最近的位置做加一操作。

int lowbit(int x);
int sum(int end_);
void add(int i, int elem);
int arr[100010]; //用于存在数组“C”中对应的下标，数组 "arr" 的下标表示电影的编号
int c[200010];   //树状数组所用的
int n, m;
int main()
{
    int t, i, a;
    scanf("%d", &t);
    for (; t > 0; t--)
    {
        memset(arr, 0, sizeof(arr));
        memset(c, 0, sizeof(c));
        scanf("%d%d", &n, &m);
        for (i = m + 1; i <= m + n; i++) //初始化两个数组
        {
            add(i, 1);      //表示将这部电影放在i这个位置
            arr[i - m] = i; //存下当前这部电影在C数组中所在的位置, 这里的 (i-m)表示电影的编号
        }
        int min_ = m, flag = 0;
        for (i = 0; i < m; i++)
        {
            scanf("%d", &a);
            if (flag) //控制输出的格式
            {
                printf(" ");
                flag = 1;
            }
            printf("%d", sum(arr[a] - 1)); //得出结果，这里之所以求出sum就是结果，是因为求的前N项和的每一项的值都是默认的为1，所以他们的和就是结果
            add(arr[a], -1);               //表示将a这部电影从原来的位置剔除
            arr[a] = min_--;               //表示将a这部电影放入新的位置，此时arr数组重新记录它的新位置
            add(arr[a], 1);                //表示将a这部电影放入，（更新操作）；
            flag = 1;
        }
        printf("\n");
    }
    return 0;
}

int lowbit(int x)
{
    return x & (-x);
}

int sum(int end_)
{
    int sum = 0;
    while (end_ > 0)
    {
        sum += c[end_];
        end_ -= lowbit(end_);
    }
    return sum;
}

void add(int i, int elem)
{
    while (i <= n + m)
    {
        c[i] += elem;
        i += lowbit(i);
    }
    return;
}