bzoj 2006 超级钢琴 —

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2006

本来应该是可以用主席树，找区间最小值，取出来后再找那段区间的次小值......

但也可以只找最小值，取出来后把原来区间分裂成两个，继续找最小值，用ST表即可；

发现自己还没写过 ST 表囧...

思路同这里：https://www.cnblogs.com/CQzhangyu/p/7071394.html

自己写了半天，才10分...奋力改了改，那个 find 里面 r++ 而 l 不 ++ 的细节真奇妙...

然后就50分了...

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const xn=5e5+,inf=0x3f3f3f3f;

int n,k,L,R,t[xn],lg[xn],f[xn][],id[xn][],bin[],ans;

struct N{

    int a,b,l,r;

    bool operator < (const N &y) const

        {return t[b]-t[a]<t[y.b]-t[y.a];}

};

priority_queue<N>q;

int rd()

{

    int ret=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

    while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return f?ret:-ret;

}

void find(int l,int r,int &y)

{

    int g=lg[r-l+];//

    r++;//!!!!!

//    printf("id[%d][%d]=%d\n",l,g,id[l][g]);

    if(t[id[r][g]]<t[id[l+bin[g]][g]])y=id[r][g];

    else y=id[l+bin[g]][g];

//    printf("find(%d,%d)=%d\n",l,r,y);

}

int main()

{

    n=rd(); k=rd(); L=rd(); R=rd();

    bin[]=;

    for(int i=,x;i<=n;i++)x=rd(),t[i]=t[i-]+x;

    for(int i=,p,lst=;i<=n;i++)

    {

        if(i<lst*)lg[i]=lg[i-];

        else lg[i]=lg[i-]+,lst*=,bin[lg[i]]=lst;

        id[i][]=i-; f[i][]=i-;

        for(int j=;j<=;j++)

        {

            f[i][j]=f[f[i][j-]][j-];

            if(t[id[i][j-]]<t[id[f[i][j-]][j-]])id[i][j]=id[i][j-];

            else id[i][j]=id[f[i][j-]][j-];

        }

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

        if(l>r)continue;

        find(l,r,p); q.push((N){p,i,l,r});

//        printf("ps:%d,%d\n",p,i);

    }

    int cnt=,p;

    while(cnt<k)

    {

        int a=q.top().a,b=q.top().b,l=q.top().l,r=q.top().r; q.pop();

        if(l<=a-)find(l,a-,p),q.push((N){p,b,l,a-})/*,printf("ps:%d,%d\n",p,b)*/;

        if(a+<=r)find(a+,r,p),q.push((N){p,b,a+,r})/*,printf("ps:%d,%d\n",p,b)*/;

        cnt++; ans+=t[b]-t[a];

//        printf("a=%d b=%d\n",a,b);

    }

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

    return ;

}

囧

最后发现把 ans 改成 long long 就A了！！！

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const xn=5e5+,inf=0x3f3f3f3f;

int n,k,L,R,t[xn],lg[xn],f[xn][],id[xn][],bin[];

long long ans;

struct N{

    int a,b,l,r;

    bool operator < (const N &y) const

        {return t[b]-t[a]<t[y.b]-t[y.a];}

};

priority_queue<N>q;

int rd()

{

    int ret=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

    while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return f?ret:-ret;

}

void find(int l,int r,int &y)

{

    int g=lg[r-l+];//

    r++;//!!!!!

//    printf("id[%d][%d]=%d\n",l,g,id[l][g]);

    if(t[id[r][g]]<t[id[l+bin[g]][g]])y=id[r][g];

    else y=id[l+bin[g]][g];

//    printf("find(%d,%d)=%d\n",l,r,y);

}

int main()

{

    n=rd(); k=rd(); L=rd(); R=rd();

    bin[]=;

    for(int i=,x;i<=n;i++)x=rd(),t[i]=t[i-]+x;

    for(int i=,p,lst=;i<=n;i++)

    {

        if(i<lst*)lg[i]=lg[i-];

        else lg[i]=lg[i-]+,lst*=,bin[lg[i]]=lst;

        id[i][]=i-; f[i][]=i-;

        for(int j=;j<=;j++)

        {

            f[i][j]=f[f[i][j-]][j-];

            if(t[id[i][j-]]<t[id[f[i][j-]][j-]])id[i][j]=id[i][j-];

            else id[i][j]=id[f[i][j-]][j-];

        }

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

        if(l>r)continue;

        find(l,r,p); q.push((N){p,i,l,r});

//        printf("ps:%d,%d\n",p,i);

    }

    int cnt=,p;

    while(cnt<k)

    {

        int a=q.top().a,b=q.top().b,l=q.top().l,r=q.top().r; q.pop();

        if(l<=a-)find(l,a-,p),q.push((N){p,b,l,a-})/*,printf("ps:%d,%d\n",p,b)*/;

        if(a+<=r)find(a+,r,p),q.push((N){p,b,a+,r})/*,printf("ps:%d,%d\n",p,b)*/;

        cnt++; ans+=t[b]-t[a];

//        printf("a=%d b=%d\n",a,b);

    }

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

    return ;

}

但已经模仿了TJ啦...处理的时候果然要带上自己，不然各种不方便...

别忘了开 long long ！因为是多段区间的和！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const xn=5e5+,inf=0x3f3f3f3f;

int n,k,L,R,t[xn],lg[xn],id[xn][];

long long ans;

struct N{

    int a,b,l,r;

    bool operator < (const N &y) const

        {return t[b]-t[a]<t[y.b]-t[y.a];}

};

priority_queue<N>q;

int rd()

{

    int ret=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

    while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return f?ret:-ret;

}

int mn(int a,int b){return t[a]<t[b]?a:b;}

int find(int l,int r)

{

    if(l>r)return -;

    int g=lg[r-l+];

    return mn(id[l][g],id[r-(<<g)+][g]);

}

int main()

{

    n=rd(); k=rd(); L=rd(); R=rd();

    for(int i=;i<=n;i++)lg[i]=lg[i>>]+;

    for(int i=,x;i<=n;i++)x=rd(),t[i]=t[i-]+x,id[i][]=i;//

    for(int j=;(<<j)<=n;j++)

        for(int i=;i+(<<j)-<=n;i++)//0  //-1

            id[i][j]=mn(id[i][j-],id[i+(<<(j-))][j-]);

    for(int i=L;i<=n;i++)q.push((N){find(max(i-R,),i-L),i,max(i-R,),i-L});

    int cnt=,p;

    while(cnt<k)

    {

        int a=q.top().a,b=q.top().b,l=q.top().l,r=q.top().r; q.pop();

        cnt++; ans+=t[b]-t[a];

        int c=find(l,a-),d=find(a+,r);

        if(c!=-)q.push((N){c,b,l,a-});

        if(d!=-)q.push((N){d,b,a+,r});

    }

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

    return ;

}

巴特西

bzoj 2006 超级钢琴 —— ST表

最新文章

热门文章