所求的Z序列为6,7,8,13,14,15,18.
R=13
这里是hyh的题解及严谨证明
这里是Candy?的做法及证(瞎)明(猜)：
貌似可以在坐标系里画出来啊
<好烦啊先不管了
如果a递增，那就是0啊
如果只能选一个纵坐标，那一定是a的中位数啊(反证应该谁都会吧)
但本题给了我们更多的机会，往左可以多选几个比中位数小的点，往右可以选几个多的
所以最优情况就应该是选了一个或多个递增的某个区间的中位数
证(猜)毕(完)
每加入一个点形成一个区间，与上一个区间比较，如果上一个区间的中位数大(那么就不满足递增了)就把这个点和上一个区间合并，继续让这个区间和上个区间比较
维护区间中位数可以用左偏树，因为合并后中位数只会减小，所以维护一个大根堆，size>区间大小一半就弹出
rt[]保存了每个区间用的左偏树的根
<变成<=用到了常见技巧 -i
注意：一开始记录区间l和r时写成了l[rt[p]]应该是l[p]
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define lc t[x].l #define rc t[x].r typedef long long ll; const int N=1e6+5,INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f; } int n,a[N]; struct node{ int l,r,v,d,size; node(){l=r=v=d=size=0;} }t[N]; int sz; int Merge(int x,int y){ if(x==0||y==0) return x|y; if(t[x].v<t[y].v) swap(x,y); rc=Merge(rc,y); t[x].size=t[lc].size+t[rc].size+1; if(t[lc].d<t[rc].d) swap(lc,rc); t[x].d=t[rc].d+1; return x; } inline int nw(int v){ t[++sz].v=v; t[sz].size=1; return sz; } inline int top(int x){return t[x].v;} inline int size(int x){return t[x].size;} inline void pop(int &x){x=Merge(lc,rc);} ll ans; int rt[N],p,l[N],r[N],tot[N]; void solve(){ for(int i=1;i<=n;i++){ rt[++p]=nw(a[i]); l[p]=r[p]=i;tot[p]=1; while(p-1&&top(rt[p-1])>top(rt[p])){ rt[p-1]=Merge(rt[p-1],rt[p]); p--; r[p]=i; while(size(rt[p])>(r[p]-l[p]+2)/2) pop(rt[p]); } } for(int i=1;i<=p;i++) for(int j=l[i];j<=r[i];j++) ans+=abs(a[j]-top(rt[i])); printf("%lld",ans); } int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++) a[i]=read()-i; t[0].d=-1; solve(); return 0; }
BZOJ 1367: [Baltic2004]sequence [可并堆 中位数]
原文：http://www.cnblogs.com/candy99/p/6288123.html