BZOJ1926：[SDOI2010]粟粟的书架—

http://www.lydsy.com/JudgeOnline/problem.php?id=1926

https://www.luogu.org/problemnew/show/P2468

幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢Thomas H. Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j页厚。

粟粟每天除了读书之外，还有一件必不可少的工作就是摘苹果，她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低，但无论如何凭粟粟自己的个头都难以摘到。不过她发现，如果在脚下放上几本书，就可以够着苹果；她同时注意到，对于第i天指定的那个苹果，只要她脚下放置书的总页数之和不低于Hi，就一定能够摘到。

由于书架内的书过多，父母担心粟粟一天内就把所有书看完而耽误了上幼儿园，于是每天只允许粟粟在一个特定区域内拿书。这个区域是一个矩形，第i天给定区域的左上角是上数第x1i行的左数第y1i本书，右下角是上数第x2i行的左数第y2i本书。换句话说，粟粟在这一天，只能在这﹙x2i－x1i＋1﹚×﹙y2i－y1i＋1﹚本书中挑选若干本垫在脚下，摘取苹果。

粟粟每次取书时都能及时放回原位，并且她的书架不会再撤下书目或换上新书，摘苹果的任务会一直持续M天。给出每本书籍的页数和每天的区域限制及采摘要求，请你告诉粟粟，她每天至少拿取多少本书，就可以摘到当天指定的苹果。

对于50%的数据，满足R, C≤200，M≤200,000；

另有50%的数据，满足R＝1，C≤500,000，M≤20,000；

不看数据范围我怕不是就要想二维主席树了……

首先我们有一个很简单的贪心：取书从大到小取的话书的数量最小。

然后先考虑后50%就是一个区间，主席树维护一下查询后缀比h大的最小数字个数即可，做法很经典就不讲了。

对于前50%的数据我们可以二分取书的最小页数，这样有a[i][j][k],b[i][j][k]分别表示(i,j)前缀和矩阵中大于等于k页的书的个数和页数和为多少。

根据贪心原则处理出最小页数之后利用a和b数组搞搞就行了。

PS：请注意可能多算/少算的书。query的最后一行和前50%最后的sum1就是起这个作用的。

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

const int N=5e5+;

const int M=;

const int MAX=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct tree{

    int l,r,size,sum;

}tr[N*];

int rt[N],pool;

inline void insert(int &y,int &x,int l,int r,int p){

    tr[x=++pool]=tr[y];

    if(l==r){

    tr[x].size++;tr[x].sum+=p;

    return;

    }

    int mid=(l+r)>>;

    if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p);

    else insert(tr[y].r,tr[x].r,mid+,r,p);

    tr[x].sum=tr[tr[x].l].sum+tr[tr[x].r].sum;

    tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size;

}

inline int query(int nl,int nr,int l,int r,int k){

    int ans=;

    while(l<r){

    int mid=(l+r)>>;

    int delta=tr[tr[nr].r].sum-tr[tr[nl].r].sum;

    if(delta<k){

        ans+=tr[tr[nr].r].size-tr[tr[nl].r].size;

        k-=delta;r=mid;

        nl=tr[nl].l;nr=tr[nr].l;

    }else{

        l=mid+;

        nl=tr[nl].r;nr=tr[nr].r;

    }

    }

    ans+=k/l+(k%l?:);

    return ans;

}

int p[M][M],a[M][M][MAX+],b[M][M][MAX+];

int main(){

    int r=read(),c=read(),m=read();

    if(r==){

    for(int i=;i<=c;i++)

        insert(rt[i-],rt[i],,MAX,read());

    for(int i=;i<=m;i++){

        int x1=read(),y1=read(),x2=read(),y2=read(),h=read();

        if(tr[rt[y2]].sum-tr[rt[y1-]].sum<h)puts("Poor QLW");

        else printf("%d\n",query(rt[y1-],rt[y2],,MAX,h));

    }

    }else{

    for(int i=;i<=r;i++){

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

        p[i][j]=read();

        }

    }

    for(int i=;i<=r;i++){

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

        for(int k=;k<=MAX;k++){

            a[i][j][k]=a[i][j-][k]+a[i-][j][k]-a[i-][j-][k];

            b[i][j][k]=b[i][j-][k]+b[i-][j][k]-b[i-][j-][k];

            if(p[i][j]>=k)a[i][j][k]++,b[i][j][k]+=p[i][j];

        }

        }

    }

    for(int i=;i<=m;i++){

        int x1=read(),y1=read(),x2=read(),y2=read(),h=read();

        int l=,r=;x1--;y1--;

        while(l<r){

        int mid=(l+r+)>>;

        if(b[x1][y1][mid]+b[x2][y2][mid]-b[x2][y1][mid]-b[x1][y2][mid]>=h)

            l=mid;

        else r=mid-;

        }

        if(!l)puts("Poor QLW");

        else{

        int sum1=b[x1][y1][l]+b[x2][y2][l]-b[x2][y1][l]-b[x1][y2][l]-h;

        int sum2=a[x1][y1][l]+a[x2][y2][l]-a[x2][y1][l]-a[x1][y2][l];

        printf("%d\n",sum2-sum1/l);

        }

    }

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ1926：[SDOI2010]粟粟的书架——题解

最新文章

热门文章