给定一个整数序列 a1?,a2?,⋅⋅⋅,an? ，求出一个递增序列 b1?<b2?<⋅⋅⋅<bn? ，使得序列 ai? 和 bi? 的各项之差的绝对值之和 ∣a1?−b1?∣+∣a2?−b2?∣+⋅⋅⋅+∣an?−bn?∣ 最小。
输入格式：
第一行为数字 n (1≤n≤10^6) ，接下来一行共有 n 个数字，表示序列 a_i (0≤a_i≤2×10^9) 。
输出格式：
第一行输出最小的绝对值之和。
第二行输出序列 bi? ，若有多种方案，只需输出其中一种。
【数据范围】
40%的数据 n≤5000
60%的数据 n≤300000
100%的数据 n≤1000000 , 0≤a_i≤2×10^9
题目来源： Baltic OI 2004 Day1, Sequence
分析：
不得不说，一道左偏树神仙题。一开始看到这道题，基本上想到的都是数学方法，或者是想到线段树之类的数据结构。后面才知道是一篇论文题，思路实在巧妙。
以下直接引用网上唯一一篇题解的思路，这里蒟蒻就只放代码：
1.观察到如果a数列递增，b数列一个一个相等就好了，a数列如果递减，b数列即为a数列的中位数。
2.考虑从1得得到一些解题的思路，把整个a划分为每一段的解都相同的m段，那么每一段都是同一个答案，那么我们看可不可以合并这些序列（因为最后要求答案是不递减的），如果前一段的b小于等于后一段的b可以直接合并，然后不管，但是如果前一段的b大于后一段的b，那么前一段的b要减，后一段的b要加才可以满足题目的限制。
3.现在我们想要怎样才能合并不满足限制的两段，首先先证明一个问题，对于任意一个序列a[1],a[2],…,a[n]，如果最优解为 (u,u,…,u)，那么在满足u≤u′≤b[1] 或b[n]≤u′≤u的情况下，(b[1],b[2],…,b[n]) 不会比 (u′,u′,…,u′) 更优，证明这个问题之后我们会发现这个序列的解改变了之后还是所有解相同的情况下最优，就可以大大地简化这个问题。
考虑如何证明：u显然是中位数，如果一段不相同的递增的解更优，则得出来u不是中位数，矛盾。因为u是中位数，显然越接近u的u’更优（证毕）。
所以对于前一段的解大于后一段的情况我们要尽量使两解相同的情况下答案最小，几何意义可知又是在中位数得时候最小。
4.现在可以建立一个基本的算法模型，即一个一个地添加数字进去，区间不断合并，直到b1≤b2≤…≤bmb1≤b2≤…≤bm为止。考虑如何去维护中位数，发现原本情况下即满足b1≤b2≤…≤bm−1b1≤b2≤…≤bm−1，如果新添加了一个数使得开始不满足限制，可以发现新的区间的前一半全部包括在了前面每一段的前半截和新添加的数字里面，这样就可以用可并堆维护了。
5.回到最前面的那个问题，题目要求严格递增怎么办？贪心地选一下，即相邻两数差1，我们把a数列每个数减去自己的下标，做到了相邻两个数差1，这样便可以按照之前原来的做法来做了（好巧妙的方法）。
Code：
1 //It is made by HolseLee on 21st June 2018 2 //Luogu.org P4331 3 #include<bits/stdc++.h> 4 using namespace std; 5 typedef long long ll; 6 const int N=1e6+7; 7 int n,top;ll b[N],ans; 8 struct Node{ 9 int l,r,top,size;ll val; 10 }stac[N]; 11 struct Leftist{ 12 int fa[N],ch[N][2],dis[N]; 13 ll val[N]; 14 int merge(int x,int y) 15 { 16 if(x==0||y==0)return x+y; 17 if(val[x]<val[y])swap(x,y); 18 ch[x][1]=merge(ch[x][1],y); 19 fa[ch[x][1]]=x; 20 if(dis[ch[x][1]]>dis[ch[x][0]]) 21 swap(ch[x][0],ch[x][1]); 22 dis[x]=dis[ch[x][1]]+1; 23 return x; 24 } 25 int del(int x) 26 { 27 fa[ch[x][0]]=fa[ch[x][1]]=0; 28 int ret=merge(ch[x][0],ch[x][1]); 29 ch[x][0]=ch[x][1]=0; 30 return ret; 31 } 32 }T; 33 inline ll read() 34 { 35 char ch=getchar();ll num=0;bool flag=false; 36 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)flag=true;ch=getchar();} 37 while(ch>=‘0‘&&ch<=‘9‘){num=num*10+ch-‘0‘;ch=getchar();} 38 return flag?-num:num; 39 } 40 void work() 41 { 42 stac[++top]=(Node){1,1,1,1,T.val[1]}; 43 for(int i=2;i<=n;i++){ 44 int l=stac[top].r+1; 45 stac[++top]=(Node){l,i,i,1,T.val[i]}; 46 while(top!=1&&stac[top].val<stac[top-1].val){ 47 --top; 48 stac[top].top=T.merge(stac[top].top,stac[top+1].top); 49 stac[top].size=stac[top].size+stac[top+1].size; 50 stac[top].r=stac[top+1].r; 51 while(stac[top].size>(stac[top].r-stac[top].l+2)/2){ 52 --stac[top].size;stac[top].top=T.del(stac[top].top);} 53 stac[top].val=T.val[stac[top].top]; 54 } 55 } 56 int cnt=1; 57 for(int i=1;i<=n;i++){ 58 while(i>stac[cnt].r)cnt++; 59 ans+=abs(T.val[i]-stac[cnt].val); 60 b[i]=stac[cnt].val+i;} 61 printf("%lld\n",ans); 62 for(int i=1;i<=n;i++) 63 printf("%lld ",b[i]); 64 } 65 int main() 66 { 67 n=read(); 68 for(int i=1;i<=n;i++){ 69 T.val[i]=read(); 70 T.val[i]-=i;} 71 work();return 0; 72 }
洛谷P4331 [BOI2004] Sequence 数字序列 [左偏树]
原文：https://www.cnblogs.com/cytus/p/9210989.html