树状数组：
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include#include #include #include #include #include #include #include #include #include #define INF 0x3fffffff #define inf -0x3f3f3f3f #define N 200010 #define M 4000010 #define LL long long #define mod 20071027 using namespace std; int n, m; int d[N + 10], arr[N / 2 + 5]; int lowbit(int x){ return x & (-x); } void add(int x, int val){ while(x <= N){ d[x] += val; x += lowbit(x); } } int sum(int x){ int s = 0; while(x > 0){ s += d[x]; x -= lowbit(x); } return s; } int main() { // freopen("in.txt", "r", stdin); int t; scanf("%d", &t); while(t --){ scanf("%d %d", &n, &m); memset(d, 0, sizeof(d)); for(int i = 1; i <= n; ++ i){ add(i, 1); arr[i] = n - i + 1; } int x; for(int i = 0; i < m; ++ i){ scanf("%d", &x); int v = sum(arr[x]); if(! i) printf("%d", n - v); else printf(" %d", n - v); if(v == n) continue; add(arr[x], -1); add(n + i + 1, 1); arr[x] = n + i + 1; } puts(""); } return 0; }