題目鏈接：[點擊打開鏈接](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; } ~~~