[BZOJ2006/Luogu2048][NOI2010]超级钢琴(贪心,堆,主席树)

发布于 2018-02-25  93 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2006/Luogu2048][NOI2010]超级钢琴(贪心,堆,主席树)

Description

小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z希望能够用这架钢琴创作出世界上最美妙的音乐。 这架超级钢琴可以弹奏出n个音符,编号为1至n。第i个音符的美妙度为Ai,其中Ai可正可负。 一个“超级和弦”由若干个编号连续的音符组成,包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的,当且仅当这两个超级和弦所包含的音符集合是相同的。 小Z决定创作一首由k个超级和弦组成的乐曲,为了使得乐曲更加动听,小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

Http

BZOJ
Luogu

Tag

贪心,堆,主席树,离散化

解决思路

考虑到需要求区间和的问题,那么求完前缀和后转化为求两个值的差最大。那么可以枚举右端点,这时就要求左端点尽量小,而对于每一个右端点,能够作为它的左端点的位置是一个固定的区间,那么可以先把区间最小值求出来,放到堆里面,每一次取出堆顶,然后再把堆顶对应的这个区间接下来小的值(比如次小值)放进堆。那么为了求出区间第\(k\)大,可以使用主席树来维护。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=500010;
const int inf=2147483647;

class Segment
{
public:
    int size;
    int ls,rs;
};

class Queue_Data
{
public:
    ll key;
    int r,kth;
};

bool operator < (Queue_Data A,Queue_Data B)
{
    return A.key<B.key;
}

int n,K,L,R;
int nodecnt=0,numcnt=0,Num[maxN];
int A[maxN],root[maxN];
Segment S[maxN*30];
priority_queue<Queue_Data> Q;

void Build(int &now,int l,int r);
void Modify(int &now,int l,int r,int pos,int key);
int Query(int r1,int r2,int l,int r,int kth);

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>K>>L>>R;
    for (int i=1;i<=n;i++) cin>>A[i+1];
    for (int i=2;i<=n+1;i++) A[i]=A[i-1]+A[i],Num[i]=A[i];
    sort(&Num[1],&Num[n+2]);//离散化
    numcnt=unique(&Num[1],&Num[n+2])-Num-1;
    Build(root[0],1,n);//建树
    for (int i=1;i<=n+1;i++)
    {
        root[i]=root[i-1];
        Modify(root[i],1,numcnt,lower_bound(&Num[1],&Num[numcnt+1],A[i])-Num,1);
    }
    for (int i=L+1;i<=n+1;i++)//先把每一个合法的区间最小找到并丢入堆中
    {
        int pos=Query(root[max(0,i-R-1)],root[i-L],1,numcnt,1);
        Q.push((Queue_Data){A[i]-Num[pos],i,1});
    }
    ll Ans=0;
    int cnt=0;
    for (int tt=1;tt<=K;tt++)//取出最大,并把区间的下一个丢入堆中
    {
        Queue_Data u=Q.top();Q.pop();
        Ans+=u.key;
        int r=u.r,kth=u.kth;
        if (kth<(r-L)-max(0,r-R-1))
        {
            int pos=Query(root[max(0,r-R-1)],root[r-L],1,numcnt,kth+1);
            Q.push((Queue_Data){A[r]-Num[pos],r,kth+1});
        }
    }
    printf("%lld\n",Ans);
    return 0;
}

void Build(int &now,int l,int r)
{
    now=++nodecnt;
    if (l==r) return;
    int mid=(l+r)>>1;
    Build(S[now].ls,l,mid);
    Build(S[now].rs,mid+1,r);
    return;
}

void Modify(int &now,int l,int r,int pos,int key)
{
    S[++nodecnt]=S[now];now=nodecnt;
    if (l==r){
        S[now].size++;return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid) Modify(S[now].ls,l,mid,pos,key);
    else Modify(S[now].rs,mid+1,r,pos,key);
    S[now].size=S[S[now].ls].size+S[S[now].rs].size;
    return;
}

int Query(int r1,int r2,int l,int r,int kth)
{
    if (l==r) return l;
    int mid=(l+r)>>1;
    int lsize=S[S[r2].ls].size-S[S[r1].ls].size;
    if (lsize>=kth) Query(S[r1].ls,S[r2].ls,l,mid,kth);
    else return Query(S[r1].rs,S[r2].rs,mid+1,r,kth-lsize);
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2006/Luogu2048][NOI2010]超级钢琴(贪心,堆,主席树)


HNCJ OIer