C18 左偏树 P4331 [BalticOI 2004] 数字序列

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1000010;
int n,top;
struct segment{ //段的信息
  int rt;  //中位数
  int r;   //段的右端
  int siz; //剩余元素的个数
}s[N];
int lc[N],rc[N],dis[N],a[N],b[N]; //左偏树

int merge(int x,int y){ //合并堆
  if(!x || !y) return x+y;
  if(a[x]<a[y]) swap(x,y); //大根堆
  rc[x]=merge(rc[x],y);
  
  if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]);
  dis[x]=dis[rc[x]]+1;
  return x; //返回合并堆的根
}
int del(int x){ //删除堆顶
  return merge(lc[x],rc[x]);
}
int main(){
  scanf("%d",&n); dis[0]=-1;
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]), a[i]-=i; //转换求不降序列
  for(int i=1;i<=n;i++){
    s[++top]=(segment){i,i,1}; //每个数看做一段
    while(top>1 && a[s[top-1].rt]>a[s[top].rt]){
      s[top-1].rt=merge(s[top-1].rt, s[top].rt);
      s[top-1].r=s[top].r; 
      s[top-1].siz+=s[top].siz;
      top--;
      while(s[top].siz>(s[top].r-s[top-1].r)/2+1){
        s[top].rt=del(s[top].rt);
        s[top].siz--;
      }
    }
  }
  for(int i=1,j=1; i<=top; i++)
    while(j<=s[i].r) b[j++]=a[s[i].rt];
  long long res=0;
  for(int i=1; i<=n; i++) res+=abs(a[i]-b[i]);
  printf("%lld\n",res);
  for(int i=1; i<=n; i++) printf("%d ",b[i]+i);
}