UVA 1513 – Movie collection（树状数组）
最后更新于：2022-04-01 15:53:36
题目链接：[点击打开链接](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=502&problem=4259&mosmsg=Submission+received+with+ID+16725571)
题意： 有编号1~n的n个影碟从上到下排列， 每次取一个影碟并把其放在最上面， 求每次取之前该影碟前面有多少个影碟。
取出影碟， 将该位置-1即可， 容易想到用树状数组来维护， 但是还要放到最前面。 其实解决方法很简单， 就是把数组开大一点， 前面留出足够大的空间， 不断更新位置即可。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 200000 + 10;
int T,n,v,m,bit[maxn],pos[maxn>>1];
int sum(int x) {
int ans = 0;
while(x > 0) {
ans += bit[x];
x -= x & -x;
}
return ans;
}
void add(int x, int d) {
while(x <= n + m) {
bit[x] += d;
x += x & -x;
}
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
memset(bit, 0, (n+m+1)*sizeof(bit[0]));
int cnt = m;
for(int i=1;i<=n;i++) {
pos[i] = i+m;
add(pos[i], 1);
}
for(int i=0;i<m;i++) {
scanf("%d",&v);
printf("%d%c", sum(pos[v]-1), i == m-1 ? '\n' : ' ');
add(pos[v], -1);
pos[v] = cnt--;
add(pos[v], 1);
}
}
return 0;
}
~~~