範例程式碼 uva1513
//uva1513
/// fake segment tree
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXNODE 524287
#define BASE 262144
/// 2^18 = 262144
/// 2^19 = 524288
using namespace std;
int N, M, q, base, nxtp, curp, newp, cnt;
int n[530000];
int p[100005];
void solve() {
nxtp = BASE + N; /// index of the empty leftmost leaf node
memset(n, 0, sizeof(n));
/// initial leaf node
for (int i = 0; i < N; i++)
n[BASE + i] = 1;
/// initial internal node
for (int i = BASE - 1; i >= 1; i--)
n[i] = n[i * 2] + n[i * 2 + 1];
/// initial place
for (int i = N; i >= 1; i--)
p[i] = BASE + (N - i);
for (int i = 0; i < M; i++, nxtp++) {
scanf("%d", &q);
/// query(q,infinite)
cnt = 0;
int l = p[q], r = MAXNODE;
for (; l^r^1; l >>= 1, r >>= 1) {
if(!(l & 1))
cnt += n[l + 1];
if (r & 1)
cnt += n[r - 1];
}
if (i != 0) printf(" ");
printf("%d", cnt);
/// remove(q)
curp = p[q];
while(curp != 0) {
--n[curp];
curp /= 2;
}
/// update(q)
p[q] = newp = nxtp;
while(newp != 0) {
++n[newp];
newp /= 2;
}
}
printf("\n");
}
int main() {
int t;
scanf("%d", &t);
for (int i = 0; i < t; i++) {
scanf("%d%d", &N, &M);
solve();
}
return 0;
}