https://www.luogu.com.cn/problem/T107073
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
小葱同学在听小学数学老师讲了如何用归并排序求逆序对之后，就觉得这东西还不如跑一个线段树来做。但是这天，小葱的语文老师告诉小葱这么一个问题：我们原来是给定NN个数，然后通过归并排序在合并左右区间的时候，求出了左右两个区间之间形成了多少个逆序对。那如果我们现在换一个问题，现在我们是告 诉了你每次合并左右区间的时候的产生的逆序对数量， 你能不能把原有的序列复现出来呢？关于更多细节，请参考数据规模与约定的部分。
别参考了知道这个意思就行
(=============================================)
因为我们只需要构造一组解
所以说 在归并排序合并操作的时候
分左边 右边两个区间
假设这个区间合并时应该要(v)个逆序对
不妨右边前(v/mid)个全都为最小,这样右边前(v/mid)个每个都贡献(mid)个逆序对
然后让(v/mid + 1)这个位置贡献(v%mid)个，
剩下的从(v/mid + 2)到(r)都贡献0
这样对每个合并操作都满足了(v)贡献
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
int n;
int z[N], y[N];
void merge_sort(int l, int r) {
if(l == r) return ;
int mid = (l + r) >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);
int v; scanf("%d", &v);
int p = l, p1 = l, p2 = mid + 1;
while(v >= mid - p1 + 1) {
y[p++] = z[p2++];
v -= mid - p1 + 1;
}
for(int i = p1; i <= mid - v; i++) y[p++] = z[p1++];
if(p2 <= r) y[p++] = z[p2++];
while(p1 <= mid) y[p++] = z[p1++];
while(p2 <= r) y[p++] = z[p2++];
for(int i = l; i <= r; i++) z[i] = y[i];
}
int main() {
cin>>n;
for(int i = 1; i <= n ;i++) z[i] = i;
merge_sort(1, n);
for(int i = 1;i <= n; i++) y[z[i]] = i;
for(int i= 1; i <= n ; i ++) printf("%d ", y[i]);
}