【题解】 bzoj2006: [NOI2010]超级钢琴 （ST表+贪心）

时间：2021-03-28 05:54:35

题面戳我

Solution

Attention

  • 哇痛苦，一直不会打\(ST\)表，我是真的菜啊qwq
  • 预处理
  Log[1]=0;two[0]=1;

  for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;

  for(int i=1;i<=24;i++)two[i]=two[i-1]*2;

  for(int i=1;i<=n;i++)ST[i][0]=i;

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

    for(int j=0;j+two[i]<=n+1;j++){

      ST[j][i]=mina(ST[j][i-1],ST[j+two[i-1]][i-1]);

    }

  }
  • 我是真的菜qwq

Code

//It is coded by ning_mew on 7.19

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn=5e5+7,inf=(1<<31);

int n,k,L,R;

int Log[maxn],ST[maxn][25];

LL sum[maxn],two[25],ans=0;

struct Node{

  LL sum;int r,nl,nr,M;

  friend bool operator < (const Node &A,const Node &B){return A.sum<B.sum;}

};

priority_queue<Node>Q;

int mina(int x,int y){

  if(sum[x]<sum[y])return x;return y;

}

int quary(int x,int y){

  int kkk=Log[y-x+1];

  return mina(ST[x][kkk],ST[y-two[kkk]+1][kkk]);

}

int main(){

  scanf("%d%d%d%d",&n,&k,&L,&R);

  Log[1]=0;two[0]=1;

  for(int i=1;i<=n;i++){scanf("%lld",&sum[i]);sum[i]+=sum[i-1];}

  for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;

  for(int i=1;i<=24;i++)two[i]=two[i-1]*2;

  for(int i=1;i<=n;i++)ST[i][0]=i;

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

    for(int j=0;j+two[i]<=n;j++){

      ST[j][i]=mina(ST[j][i-1],ST[j+two[i-1]][i-1]);

    }

  }

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

    int l=max(0,i-R),r=i-L;

    Node box;box.r=i;box.nl=l;box.nr=r;

    box.M=quary(l,r);box.sum=sum[i]-sum[box.M];

    Q.push(box);

  }

  while(k){

    k--;Node box=Q.top();Q.pop();

    ans+=box.sum;

    Node A,B;

    if(box.nl<box.M){

      A.nl=box.nl;A.nr=box.M-1;A.M=quary(A.nl,A.nr);

      A.r=box.r;A.sum=sum[A.r]-sum[A.M];

      Q.push(A);

    }

    if(box.M<box.nr){

      B.nl=box.M+1;B.nr=box.nr;B.M=quary(B.nl,B.nr);

      B.r=box.r;B.sum=sum[B.r]-sum[B.M];

      Q.push(B);

    }

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

  return 0;

}

博主蒟蒻，随意转载。但必须附上原文链接：http://www.cnblogs.com/Ning-Mew/，否则你会场场比赛暴0！！！

相关文章