归并排序

小葱同学在听小学数学老师讲了如何用归并排序求逆序对后，就觉得这东西还不如跑一个线段树来做。但是这天，小葱的语文老师告诉小葱这么一个问题：我们原来是给定N个数，然后通过归并排序在合并左右区间的时候，求出了左右区间之间形成了多少个逆序对。那么如果我们现在换一个问题，现在我们是告诉了你每次合并左右区间的时候产生的逆序对数量，你能不能把原有的序列复现出来呢？关于更多的细节，请参考数据规模与约定的部分。

【输入格式】

第一行一个整数N 代表数的个数

接下来一行若干个数，代表每次区间合并左右区间的时候所产生的逆序对个数。

【输出格式】

输出一行N个数，代表一组合法的方案。你需要保证你输出的是1—N的排列

【样例】

1 2

【样例】

3 2 1

【数据规模与约定】

对于40%的数据，(N leq 10)

对于70%的数据，(N leq 100)

对于100%的数据，(1leq N leq 10^5)，保证至少有一组合法解，读入的数不超过int

关于输入的格式，可以参考随题面下发的归并排序的代码。这段代码会根据出入的1—N的排列，按顺序产生每次合并是产生的逆序对个数。这些数值便是这个题除了N以外的输入信息。

Solution

考虑归并排序的步骤。每次从两个集合里找较小的数。如果右边的比左边的小，就会产生逆序对。也就是说，当右边的比左边的先拿出来的时候，会对答案有贡献。那么，加入当前数x会产生y的贡献，当且仅当左边的序列里还有y个数，这时候将x拿出即可。

至于怎么判断y，可以这样：只要当前的逆序对个数比左区间的个数多，就从右区间取数，直到逆序对个数不够，然后就从左区间取出几个数，使剩下的数的个数等于剩余逆序对的个数，然后再从右区间取一个数，剩余的按左右区间的顺序取走就行了。

然后就相当于给所有的数的位置排了序。最后再按照这个顺序还原数列就好了

#include <iostream>
#include <cstdio>
using namespace std;
inline long long read() {
  long long x = 0; int f = 0; char c = getchar();
  while (c < '0' || c > '9') f |= c == '-', c = getchar();
  while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return f ? -x : x;
}

int n, a[100005], b[100005];
inline void bsort(int l, int r) {
  if (l == r) return;
  int m = (l + r) >> 1;
  bsort(l, m); bsort(m + 1, r);
  int p1 = l, p2 = m + 1, p = l;
  int v = read();
  while (v >= m - p1 + 1) {//不断的从右区间取数
    b[p++] = a[p2++], v -= m - p1 + 1;
  }
  for (int i = p1; i <= m - v; ++i) b[p++] = a[p1++];//从左区间取一些数
  if (p2 <= r) b[p++] = a[p2++];
  while (p1 <= m) b[p++] = a[p1++];
  while (p2 <= r) b[p++] = a[p2++];
  for (int i = l; i <= r; ++i) a[i] = b[i];
}
int main() {
  freopen("bsort.in", "r", stdin);
  freopen("bsort.out", "w", stdout);
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = i;
  bsort(1, n);
  for (int i = 1; i <= n; ++i) b[a[i]] = i;//按照位置排序
  for (int i = 1; i <= n; ++i) printf("%d ", b[i]);
  return 0;
}