Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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 a₁,..., a_m (1a_in) 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 a_i, immediately before this box is removed from the stack.

Note that after each locate request a_i, the movie box with label a_i 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

---

題目描述：

一開始堆疊內部長成 (top) 1,2,3, ..., n (bottom), 接下來有 m 筆操作，
要將數字 x 搬到 top, 並且輸出它距離 top 的距離, 然後將 x 放在 top,
模擬所有操作

題目解法：

將 stack top 的屬性當作最大, 依序遞減到 bottom, 然後操作的時候查詢有多少比它大的數字,
接著將這個數字修改成 top 的屬性+1 放入,
這麼一來就可以使用 binary indexed tree 了

#include <stdio.h>
#include <string.h>
int BIT[262144];
void modify(int idx, int v, int L) {
    while(idx <= L) {
        BIT[idx] += v;
        idx += idx&(-idx);
    }
}
int query(int idx) {
    int sum = 0;
    while(idx) {
        sum += BIT[idx];
        idx -= idx&(-idx);
    }
    return sum;
}
int main() {
    int A[100005];
    int n, m, i, j;
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        memset(BIT, 0, sizeof(BIT));
        int L = n+m;
        for(i = 1, j = n; i <= n; i++, j--) {
            A[i] = j;
            modify(A[i], 1, L);
        }
        int x, l, size = n;
        for(i = 0; i < m; i++) {
            scanf("%d", &x);
            l = query(A[x]);
            if(i)   putchar(' ');
            printf("%d", n-l);
            modify(A[x], -1, L);
            A[x] = ++size;
            modify(A[x], 1, L);
        }
        puts("");
    }
    return 0;
}