逆序对(数)
在排列a中，若存在i<j，且ai>aj，则（ai,aj）是一个逆序对，逆序数就是数列a中逆序对的数量。
一个长度为n，元素为1-n的排列可以得到的最大的逆序数为n(n-1)/2。
假设当前排列长为n，最小数为a，则a有n种放法，放在从左到右第i个位置时会生成i-1个逆序对。
逆序数与字典序的关系
一个数列的逆序数越大，它的字典序越大。
求一个数组的逆序数有三种方法 归并排序 线段树 树状数组 这里对这三种都不做说明
这个题目让我们求一个有m个逆序对的字典序最小的排列（该排列的元素为1-n）
之前说到过字典序越大逆序数越多，所以我们只需要不断的处理该排列中最小的元素就可以。
拿样例举一个例子，5个元素有4个逆序对，我们知道4个元素最多可以产生6个逆序对>m，所以为了保证字典序最小我们只需要把1放在开头，当1确定以后，问题就转换成了求2-5这4个元素的字典序最小的排列，那么同理，3个元素最多可以产生3个逆序对，所以2不能放在开头，不然不可能产生4个逆序对，之前说的逆序对越多字典序越大，我们就必须让剩下的数能构成的逆序对数尽量小，所以2要放到最后，这样m减少的最多。接下来处理3，这时的问题是求3-5这三个元素构成逆序对为1的字典序最小的排列，只需要重复上述步骤就可以求解最后答案为1 3 5 4 2
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <queue> 6 #include <stack> 7 #include <stdio.h> 8 #include <cmath> 9 #include <string.h> 10 #include <vector> 11 12 #define ll long long 13 using namespace std; 14 vector <int> start;//存放入开头的元素 15 vector <int> end;//存放入尾部的元素 16 int main() 17 { 18 //freopen("C:\Users\16599\Desktop\in.txt","r",stdin); 19 ll n,m; 20 cin>>n>>m; 21 for(int i=1;i<=n;i++) 22 { 23 ll k=(n-i)*(n-i-1)/2; 24 if(k>=m)//如果剩下的元素构成的最大逆序对的数量大于m,则把该元素放在开头 25 start.push_back(i); 26 else//否则放到结尾，并且更新m 27 { 28 end.push_back(i); 29 m=m-(n-i); 30 } 31 } 32 for(int i=0;i<start.size();i++)//输出该排列 33 cout<<start[i]<<" "; 34 for(int j=end.size()-1;j>=0;j--) 35 cout<<end[j]<<" "; 36 return 0; 37 }