[BOI2004]Sequence 数字序列

Description：

Hint:

\(n<=10^5\)

Solution：

首先考虑b不严格递增时的做法

发现当\(a[i]\)递增时\(b[i]\)直接取\(a[i]\)即可，否则此时需要对之前的答案和现在的答案取中位数

如果做中位数操作之后还是小于前面的答案，就一直取中位数

最后会得到许多段值递增的区间，每一段区间里的数都对应这个答案

至于题目要求的严格递增，输入\(a\)序列时每个数减去其下标，输出答案时加回来即可

由于本题需要动态地向合并序列的中位数，故采用左偏树实现

#include<bits/stdc++.h>

using namespace std;

const int mxn=1e6+5;

int n,l[mxn],r[mxn],tot[mxn],a[mxn],b[mxn],sz[mxn],dis[mxn]={-1},ch[mxn][2],val[mxn],rt[mxn];

namespace Heap {

    int merge(int x,int y) {

        if(!(x&&y)) return x+y;

        if(val[x]<val[y]) swap(x,y);

        ch[x][1]=merge(ch[x][1],y);

        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;

        if(dis[ch[x][1]]>dis[ch[x][0]])

            swap(ch[x][0],ch[x][1]);

        dis[x]=dis[ch[x][1]]+1;

        return x;

    }

}

using namespace Heap;

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;++i) scanf("%d",val+i),val[i]-=i;

    int now=0;

    for(int i=1;i<=n;++i) {

        ++now; l[now]=r[now]=rt[now]=i;

        tot[now]=sz[rt[now]]=1;

        while(now>1&&val[rt[now-1]]>val[rt[now]]) {

            --now; r[now]=r[now+1],tot[now]+=tot[now+1];

            rt[now]=merge(rt[now],rt[now+1]);

            while(sz[rt[now]]*2>tot[now]+1)

                rt[now]=merge(ch[rt[now]][0],ch[rt[now]][1]);

        }

    }

    long long ans=0;

    for(int i=1;i<=now;++i)

        for(int j=l[i];j<=r[i];++j)

            ans+=1ll*abs(val[rt[i]]-val[j]);

    printf("%lld\n",ans);

    for(int i=1;i<=now;++i)

        for(int j=l[i];j<=r[i];++j)

            printf("%d ",val[rt[i]]+j);

    return 0;

}

巴特西

[BOI2004]Sequence 数字序列

Description：

Hint:

Solution：

最新文章

热门文章