BZOJ 1367 [Baltic2004]sequence 可并堆

题意:链接方法:可并堆解析:wzc讲的第二道可并堆？不这是第一道，然后之前他好像还讲了个双堆求中位数？大概想想，是不是就是维护一个小根堆以及一个大根堆，之后每次来元素，比中位数大就加到小根堆，比中位数小就加到大根堆，之后如果两堆差超过了2，就往少的里加，之后元素多的堆里的堆顶元素是新中位数？好像是吧我也没太听，不过自己YY这感觉像是对的？反正我不会写堆以上与本题无关接下来说本题：首先让我们这么想，如果一个递增序列，那么它的对应选取的序列就是其本身，对答案没有贡献，如果一个递减序列，那么答案是什么呢？是中位数。证明请出门左转找数学竞赛的同志。所有的元素，我们可以看做将其分为若干个线段，每一个线段都有一个中位数，最终将所有的答案加到一起就是结果。然后具体怎么处理呢？首先有一个新的元素来了，我们把它看做一个新的堆，之后呢，我们要观察这个堆与前面的堆有没有什么关系，如果当前这个堆的中位数的值比前一个堆的中位数的值要小，那么就不满足递增性质了，所以我们需要将这两个堆合并。然后就处理完了，最后统计答案。另外，对于这些中位数，我们维护出来的可能不满足严格递增，有可能是含不下降的，然而这个怎么处理呢？听说是将a[i]-i，，好像是这样？这样是把不下降转为递增？这里我写的是大根堆，好像小根堆也可以？但是总感觉讨论的时候复杂啊。代码:;ll;int ch[N][2],key[N],size[N],root[N],h[N],L[N],R[N],w[N],num[N],a[N];int n,m,x,tot,cnt;void pushup(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}int merge(int x,int y){if(!x)return y;if(!y)return x;if(key[x]<key[y])swap(x,y);ch[x][1]=merge(ch[x][1],y);pushup(x);if(h[ch[x][0]]<h[ch[x][1]])swap(ch[x][0],ch[x][1]);if(!h[ch[x][1]])h[x]=0;else h[x]=h[ch[x][1]]+1;return x;}int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++)scanf(“%d”,&a[i]),a[i]-=i;for(int i=1;i<=n;i++){root[++tot]=++cnt;key[cnt]=a[i],size[cnt]=1;num[tot]=1,L[tot]=R[tot]=i;while(tot>1&&key[root[tot]]<key[root[tot-1]]){tot–;root[tot]=merge(root[tot],root[tot+1]);R[tot]=R[tot+1];num[tot]+=num[tot+1];while(size[root[tot]]>(num[tot]+1)/2){root[tot]=merge(ch[root[tot]][0],ch[root[tot]][1]);}}}ll ans=0;for(int i=1;i<=tot;i++){for(int j=L[i];j<=R[i];j++){ans+=abs(key[root[i]]-a[j]);}}printf(“%lld\n”,ans);}

走过的路成为背后的风景，不能回头不能停留，若此刻停留，