题解 P4331 【[BOI2004]Sequence 数字序列】
Nemlit
2019-02-07 22:22:00
PS：参考了黄源河的论文《左偏树的特点及其应用》
[原文地址](https://www.cnblogs.com/bcoier/p/10355646.html)
题目描述：给定一个整数序列$a_1, a_2, … , a_n$，求一个递增序列$b_1 < b_2 < … < b_n$，使得序列$a_i$和$b_i$的各项之差的绝对值之和 $|a_1 - b_1| + |a_2 - b_2| + … + |a_n - b_n|$ 最小。
不难发现两条性质：
①：若原序列a满足$a_1 < a_2 < … < a_n$，显然最优情况为$b_i=a_i$
②：若原序列a满足$a_1 > a_2 > … > a_n$，显然最优情况为$b_{mid}=x$（x为a中位数）
有了上述的两种情况，不难发现，整个a序列是尤一些单调区间组成。
所以我们可以将原序列a拆成若干个单调区间，最后再将答案合并。
那两段区间的答案怎么合并呢？
我们可以重新找一个中位数来合并即可。
不断的找中位数，不难想到[这道题](https://www.luogu.org/problemnew/show/P1168)，可是那道题是一个一个加入进堆，而现在我们要解决的是将两个堆合并来找中位数，直接上二叉堆合并复杂度为$O(n)$，所以不难想到[可并堆](https://www.luogu.org/problemnew/show/P3377)（这里使用左偏树）。
假设我们已经找到前k个数的最优解，队列中有$cnt$段区间，每段区间最优解为$w_1,w_2,…,w_{cnt}$，现在要加入$a_{k+1}$，并更新队列。
首先把$a_{k+1}$加入队尾，令$w_{cnt+1}=a_{k+1}$，如果$w_{cnt}>w_{cnt+1}$，就将最后两个区间合并，并找出新区间的最优解。重复上述过程，直至满足$w$单调递增。
注意：题目要求的是一个递增序列b，可以用减下标来实现（即输入时把每个数都减去对应下标，输出时加上），这样就可以将递增序列转化成不下降序列，这样就可以保证每一段区间的序列b不一样了（原本有很多连续一段区间全是中位数，不能保证递增）。
代码如下：
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define debug printf("Now is Line : %d\n",__LINE__)
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define mod 1000000007
il int read()
{
re int x=0,f=1;re char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return x*f;
}
#define _ 1000006
int n,dis[_],ch[_][2],cnt;
ll a[_],b[_],ans;
struct node{int root,ls,rs,size,val;}e[_];
il int merge(int x,int y)
{
if(!x||!y) return x+y;
if(a[x]<a[y]||(a[x]==a[y]&&x>y)) swap(x,y);
ch[x][1]=merge(ch[x][1],y);
if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
int main()
{
n=read(); dis[0]=-1;
for(re int i=1;i<=n;++i) a[i]=read()-i;
for(re int i=1;i<=n;++i)
{
e[++cnt]=(node){i,i,i,1,a[i]};
while(cnt>1&&e[cnt].val<e[cnt-1].val)
{
--cnt;
e[cnt].root=merge(e[cnt].root,e[cnt+1].root);
e[cnt].size+=e[cnt+1].size;
e[cnt].rs=e[cnt+1].rs;
while(e[cnt].size*2>e[cnt].rs-e[cnt].ls+2)
{
--e[cnt].size;
e[cnt].root=merge(ch[e[cnt].root][0],ch[e[cnt].root][1]);
}
e[cnt].val=a[e[cnt].root];
}
}
for(re int i=1;i<=cnt;++i)
{
for(re int j=e[i].ls;j<=e[i].rs;++j)
{
b[j]=e[i].val;
ans+=abs(a[j]-b[j]);
}
}
printf("%lld\n",ans);
for(re int i=1;i<=n;++i) printf("%lld ",b[i]+i);
return 0;
}
```