题目描述
小可可是音乐学院的一名学生，他需要经常创作乐曲完成老师布置的作业。
可是，小可可是一个懒惰的学生。所以，每次完成作业时，他不会重新创作一首新的乐曲，而是去修改上一次创作过的乐曲作为作业交给老师。小可可的乐曲由N个音调不同的音符组成，分别记为音符1…N。因此，他创作的乐曲是由1…N的一个排列构成，例如N=5时，他创作的乐曲可能为：2,1,3,5,4。但是，小可可每一次会按照一定的要求修改上一次创作的乐曲。他规定，修改过后的乐曲必须与上一次创作的乐曲的悦耳值相同。所谓悦耳值就是他所创作的乐曲，也就是1…N的排列中逆序对的个数。逆序对是指对于1…N的一个排列A1,A2,...,An中的两个数Ai,Aj，满足iAj，例如：2,1,3,5,4 这个排列中有2个逆序对，分别为：(2,1)，(5,4)。可是，满足条件的排列有很多，小可可会选择在这些满足条件的排列中字典序大于上次创作乐曲的排列的字典序，且字典序尽量小的那一个排列作为新的乐曲。这里的字典序指：排列A：A1,A2…An和排列B：B1,B2…Bn，若存在一个数k，使得Ak由于小可可最近要参加学校的篮球比赛，他没有空余时间完成老师布置的作业，于是他希望作为他好友的你帮助他完成作业。
输入格式
第1行1个正整数N，表示小可可的乐曲由N个音调不同的音符组成。
第2行为N个不同的正整数，表示1…N的一个排列，即小可可上次创作的乐曲。
输出格式
输出只有一行，为1...N的一个排列，表示你帮助小可可修改后的乐曲。
数据保证有满足条件的解。
样例输入
样例一
3
2 3 1
样例二
5
2 1 3 5 4
样例输出
样例一
3 1 2
样例二
2 1 4 3 5
solution
字典序
因为要字典序最小,所以有:若新序列P相对于原序列A第一个修改的数为Ai，则i要尽可能小,因此枚举i的时候应该从后往前枚举。枚举i，那么如何判断i位作为第一个修改的数是否可行并构造可行解呢？
如何判断一个点i 是否 可以被作为第一个被修改点
我们首先用树状数组 预处理出来p[i]，表示第i位后有几个数字比它小，sum[i]表示i-n位的逆序对数目，显然sum[i]=sum[i+1]+p[i]；
若第i个点为可以被作为第一个被修改点开始修改，则显然要满足以下条件：A[i]< MAX{A[i],A[i+1],A[i+2]…A[n]} , 即第i+1个点到第n个点中间有比第i个点大的数.
关于一段区间可产生的逆序对的数量的讨论
设后i+1位数中的逆序对数目为tot，max{num}为交换后i~n位中的逆序对最大数目，min{num}则为最小，则max{num}>=tot>=min{num}，因为要求逆序对数不变，则对于一段区间可以造出的要在可能区间内。
显然max{num}=(n-i+1)*(n-i)/2，而tot肯定小于这个min{num}是把 第i位数x 与 后面大于x的值中的最小值交换后，再把i+1n为升序排列的逆序对数目，因为此时后i+1n位间没有逆序对，而交换上来的是大于中的最小的，显然有i位产生的逆序对数最小，毕竟 最小+最小=最小。
证明:在可变范围内,我们可以随意更改一段区间的逆序对的数量.
对于一个点,它对答案的贡献值等于在这个点后面的所有点中比这个点小的数量. 假设我们交换a[i] 和 aj , 那么 1 ~ i-1 这段区间对总区间的逆序对的数量贡献值是不变的,因为不管i~n怎么排列,数字种类是不会变化的,
对于 j+1~ n 这段区间 对总区间的贡献自然也是不变的,原因是很显然的.
对于 i~j 这段区间, 我们可以证明逆序对总数加了1. 证明过程如下:因为a[j]是大于a[i]的数中最小的一个,所以在数字序列i+1~j-1这些数中比a[i] 大的数同样比a[j] 大, 比a[i] 小的数字同样比a[j] 小, 所以逆序对只增加了1.
所以,我们通过交换两个数字, 可以随意增加一段区间的逆序对数量, 同理,我们也可以随意减少一段区间的逆序对数量.
构造最优解
在构造最优解前我们要证明一件东西：若A[i]符合以上条件，则将A[i]与A[j]交换后并能够造出一种逆序对数目相同的方案，其中A[j]为i+1~n中大于A[i]的最小值。
分两步证明：
1.将A[j]放上来后由A[j]产生的逆序对数目比之前多1，即(new)p[i]=(old)p[i]+1，而后面部分产生的逆序对数又能达到最大（降序排列），即最大值>=tot。
2.因为上面的条件中有tot>=p[i]+1，所以当A[j]换上来后逆序对数的最小值小于等于原逆序对数，所以一定有一种方案使得A[j]与A[i]交换后逆序对数不变。
最后一步就是构造最优解了，假如有组数据如下：
A ： 4 1 5 3 2
P ： 3 0 2 1 0
Sum 6 3 3 1 0
2不符合“p[i]+1<=sum[i]”
3不符合“A[i]< MAX{A[i],A[i+1],A[i+2]…A[n]}”
5不符合“A[i]< MAX{A[i],A[i+1],A[i+2]…A[n]}”
1符合两个条件，我们把1 和后面的 2 交换 再把后面的是升序排列 来构造最优解
此时序列为： 4 2 1 3 5
原来后4位有sum[2]=3个逆序对,换上来升序排列后有p[2]+1=1个逆序对,还需要x=3-1=2个逆序对，因为后三位要字典序最小，我们思考1能否不变？不可以。因为C12=1 <=2 即后面3个数最大的逆序对数 >= 所需数，所以我们要改变1，那么我们把1与谁交换呢？令y=所需数x-后面最大逆序对数，此处y=2-1=1，这样将A[k]与A[k+y]交换，此处k为第一个后面的数中需要交换的数，这样就会多出y个逆序对（因为后面的数是升序排列过的），再把A[k+y+1~n]降序排列，产生最多的逆序对就可以了。
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 10000000;
const int maxn = 500005;
int t[maxn],p[maxn],mx[maxn],a[maxn],n;
ll sum[maxn];
inline int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline ll calc(ll n){return (n*(n-1))>>1;}
inline bool cmp(int a,int b){return a>b;}
inline int lowbit(int x){return x&-x;}
inline int query(int x){int ans=0; for (int i=x;i;i-=lowbit(i)) ans+=t[i];return ans;}
inline void update(int x){for (int i=x;i<=n;i+=lowbit(i)) t[i]++;}
inline void work(int pos,ll num){
ll tmp; sort(a+pos,a+n+1); //先排序,那么排序过后可以保证pos到n产生了0个逆序对
for (int i=pos;i<n;i++){//找位置
if ((tmp = calc(n-i))<num){//如果从pos+1 到 n 的最大逆序对数量无法满足,那么明显要在pos位置上搞一搞
swap(a[i],a[i+num-tmp]); sort(a+i+1,a+n+1,cmp);
for (int i=1;i<n;i++) printf("%d ",a[i]); printf("%d
",a[n]);
return;
}
}
for (int i=1;i<n;i++) printf("%d ",a[i]);cout<<a[n];
}
int main(){
n=read(); for (int i=1;i<=n;i++) a[i]=read();
for (int i=n;i;i--){p[i]=query(a[i]-1);sum[i]=sum[i+1]+p[i];mx[i]=max(mx[i+1],a[i]);update(a[i]);}
a[n+1]=inf;
for (int i=n-1;i;i--)
if (calc(n-i)+p[i]+1>=sum[i]&&p[i]+1<=sum[i]&&mx[i]>a[i]){//判断改变第i个位置可不可以成功,如果可以就更改
int pos=n+1;
for (int j=i+1;j<=n;j++) if (a[j]>a[i]&&a[j]<a[pos]) pos=j;
swap(a[i],a[pos]);
work(i+1,sum[i]-p[i]-1);//从第i+1位置开始,搞出sum[i]-p[i]-1个逆序对
return 0;
}
return 0;
}