题目描述

最开始有一个长度为 $0$ 的序列，需要对序列进行 $n$ 次操作。每次操作会给出一个整数 $x$，你需要将它加入序列并且输出这个数是从大到小排名第几个数。

因为某种特殊性质，除第一个数以外，新加的数一定和现有的数都不一样，并且与上一个数相比差不会超过 $[-m..m]$。例如 $m=10$，上一个数是 $20$，那么新加的数在 $[10..30]$ 范围内。

输入格式

从标准输入读入数据。

输入第一行包含两个正整数 $n$ 和 $m$，保证 $n \le 10^{6}$，$m \le 10^{2}$。

接下来 $n$ 行，每行一个整数 $x$，保证 $|x| \le 1000000000$ 并且 $x$ 满足特殊性质。

输出格式

输出到标准输出。

输出 $n$ 个整数，表示每次新加的数是从大到小第几个数。

样例输入

20 5
0
-5
-10
-15
-20
-16
-11
-12
-14
-18
-19
-22
-23
-21
-25
-30
-29
-28
-26
-31

样例输出

1
2
3
4
5
5
4
5
6
9
10
12
13
12
15
16
16
16
16
20

限制条件

stdc++.h
namespace
::
define
sys
asm
alloc
[
]

---

很多人用了链表，可我偏偏就要树状数组，但是样例过了之后交上去确 $WA$ 了。求调！

整体思路：树状数组 + 离散化 + 二分（这个题不能使用任何 $STL$ 工具，只能手写了emm）

我的垃圾代码：

#include <cstdio>

const int N = 1e6 + 10;
const int o = 1e6;
int n, m;
int *a = new int, *tr, *tmp;
int *b;

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

void add(int x, int y) {
	for (int i = x; i <= n; i += lowbit(i)) {
		*(tr + i) += y;
	}
}

int sum(int x) {
	int ans = 0;
	for (int i = x; i; i -= lowbit(i)) {
		ans += *(tr + i);
	}
	return ans;
}

void merge_sort(int l, int r) {
	if (l >= r) {
		return;
	}
	int mid = (l + r) / 2;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= r) {
		if (*(a + i) < *(a + j)) {
			*(tmp + k) = *(a + i);
			k++, i++;
		} else {
			*(tmp + k) = *(a + j);
			k++, j++;
		}
	}
	while (i <= mid) {
		*(tmp + k) = *(a + i);
		k++, i++;
	}
	while (j <= r) {
		*(tmp + k) = *(a + j);
		k++, j++;
	}
	for (int i = l, j = 0; i <= r; i++, j++) {
		*(a + i) = *(tmp + j);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n + 2; i++) {
		new int;
	}
	b = new int;
	for (int i = 1; i <= n + 2; i++) {
		new int;
	}
	tr = new int;
	for (int i = 1; i <= n + 2; i++) {
		new int;
	}
	tmp = new int;
	for (int i = 1; i <= n + 2; i++) {
		new int;
	}
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		*(a + i) = x;
		*(b + i) = x;
	}
	for (int i = 1; i <= n; i++) {
		*(tr + i) = 0;
		*(tmp + i) = 0;
	}
	merge_sort(0, n - 1);
	for (int i = 0; i < n; i++) {
		int l = 0, r = n - 1;
		while (l < r) {
			int mid = (l + r) / 2;
			if (*(b + i) <= *(a + mid)) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		*(b + i) = r + 1;
	}
	for (int i = 0; i < n; i++) {
		add(*(b + i), 1);
		printf("%d\n", sum(n) - sum(*(b + i)) + 1);
	}
	return 0;
}