UVa 1513 Movie collection 树状数组

题意：

有(n)个影碟，每次操作先输出编号为(x)的影碟上面有多少影碟，然后把它抽出来放在最上面。

分析：

设编号为(x)的影碟的位置为(pos_x)，每次查询前(pos_x)的前缀和，这是影碟(x)和下面影碟的数量，再用(n)减去就是答案。
然后把(pos_x)的值置为(0)，再在最后面新加一个位置，置为(1)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100000 + 10;

int n, m;
int C[maxn << 1];

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

void add(int x, int v) {
	while(x <= n + m) {
		C[x] += v;
		x += lowbit(x);
	}
}

int query(int x) {
	int ans = 0;
	while(x) {
		ans += C[x];
		x -= lowbit(x);
	}
	return ans;
}

int pos[maxn];

int main()
{
	int T; scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		memset(C, 0, sizeof(C));
		for(int i = 1; i <= n; i++) {
			pos[i] = n - i + 1;
			add(i, 1);
		}

		int tot = n;
		for(int i = 0; i < m; i++) {
			int x;
			scanf("%d", &x);
			printf("%d", n - query(pos[x]));
			add(pos[x], -1);
			add(++tot, 1);
			pos[x] = tot;
			if(i < m - 1) printf(" ");
			else printf("
");
		}
	}

	return 0;
}