思维好题-BZOJ1367-sequence-解题报告

i207M · 2018-12-20 18:12:40 · 个人记录

很神仙的题，可以用左偏树，但是有用堆的更优做法。

这是12月集训时LX将的题，日后再补题解

啊。看12月集训笔记吧。

    in(n);
    LL ans=0;
    for(ri i=1,t; i<=n; ++i)
    {
        in(t);
        t-=i;
        q.push(t);
        ans+=q.top()-t;
        q.pop();
        q.push(t);
    }
    out(ans);

有一个用左偏树的题解，大意是贪心的维护：

对于一个上升序列，答案也是上升的。

对于一个下降序列，答案是中位数。

将前边的序列分为若干段，每次插入一个数自成一段。设w为每一段的中位数，如果w[i-1]>w[i]，那么就和上一段合并。找中位数用左偏树维护size。