[BZOJ 1926] 粟粟的书架

BZOJ 传送门

Luogu 传送门

BZOJ的sillyB评测机各种无故CE，只好去Luogu上A了o(╯□╰)o

Solution:

从数据范围可以发现，这其实是2道题：

（1）一个$R*C$的矩形，每次询问一个子矩形的结果，$R,C\le 200$，$A[i][j]\le 1000$。

（2）一个$C$个数的序列，每次询问一个区间的结果，$C\le 5e5$。

1、前缀和+二分答案

找到此题的数据特点：$A[i][j]$极小，只有1000，使得$O（RC*1000）$的算法可行

于是我们维护1~i，1~j的矩形中大于k的数的个数及它们的总和，从而O（1）得出目标矩形的结果

$cnt[i][j][k]$表示行号在$[1,i]$，列号在$[1,j]$，厚度大于等于$k$的书的数目。

$sum[i][j][k]$表示行号在$[1,i]$，列号在$[1,j]$，厚度大于等于$k$的书的厚度之和。

每一次询问二分最小厚度（最小厚度是否可行具有单调性），求出值$t$，表示满足条件的情况下，最大的最小厚度。

然而由于有相同厚度，因此还要计算出厚度为$t$的书有多少本没有用上。

2、主席树

主席树解决的一类经典问题是求区间第K大的数

其实在这种背景下主席树的应用和线段树的性质关系并不大，可以理解为带了前缀和的二分查找树

由于其处理的区间具有对应关系，于是维护前缀的线段树间是可以相加减的，从而得到当前区间的信息

此题中厚度仅为1000，于是在每个点维护：

$cnt$：该前缀版本中，这个节点对应厚度区间内的书的数量。

$sum$：该前缀版本中，这个节点对应厚度区间内的书的厚度之和。

这样对答案在$root[end]-root[start-1]$的线段树中类似二分查找树地确定是进入左子树还是右子树即可

Code:

#include <bits/stdc++.h>

using namespace std;

inline int read()

{

    char ch;int num,f=0;

    while(!isdigit(ch=getchar())) f|=(ch=='-');

    num=ch-'0';

    while(isdigit(ch=getchar())) num=num*10+ch-'0';

    return f?-num:num;

}

const int MAXN=205,MAXM=1005;

const int N=5e5+10,M=1e7+10;

struct FunSeg

{

    int ls,rs,sum,cnt;

}seg[M];

int root[N],S[N],cnt;

int n,m,q,dat[MAXN][MAXN],f[MAXN][MAXN][MAXM],g[MAXN][MAXN][MAXM];

int cal_f(int x1,int y1,int x2,int y2,int k)

{

    return f[x2][y2][k]-f[x1-1][y2][k]-f[x2][y1-1][k]+f[x1-1][y1-1][k];

}

int cal_g(int x1,int y1,int x2,int y2,int k)

{

    return g[x2][y2][k]-g[x1-1][y2][k]-g[x2][y1-1][k]+g[x1-1][y1-1][k];

}

void solve1()

{

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

        for(int j=1;j<=m;j++) dat[i][j]=read();

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

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

        {

            for(int k=1;k<=1000;k++)

                f[i][j][k]=f[i-1][j][k]+f[i][j-1][k]-f[i-1][j-1][k],

                g[i][j][k]=g[i-1][j][k]+g[i][j-1][k]-g[i-1][j-1][k];

            f[i][j][dat[i][j]]+=dat[i][j];g[i][j][dat[i][j]]++;

        }

    for(int k=999;k>=1;k--)

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

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

                f[i][j][k]+=f[i][j][k+1],g[i][j][k]+=g[i][j][k+1];

    while(q--)

    {

        int x1=read(),y1=read(),x2=read(),y2=read(),h=read(),l=1,r=1000;

        while(l<=r)

        {

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

            if(cal_f(x1,y1,x2,y2,mid)>=h) l=mid+1;

            else r=mid-1;

        }

        if(!r){puts("Poor QLW");continue;};

        cout << cal_g(x1,y1,x2,y2,r)-(cal_f(x1,y1,x2,y2,r)-h)/r << endl;  //将这个厚度中多余的书减掉

    }

}

void Update(int x,int &y,int val,int l,int r)

{

    y=++cnt;seg[y]=seg[x];  //不用改变的节点沿用上一次已经完全构造完的

    seg[y].sum+=val;seg[y].cnt++;

    if(l==r) return;

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

    if(val<=mid) Update(seg[x].ls,seg[y].ls,val,l,mid);

    else Update(seg[x].rs,seg[y].rs,val,mid+1,r);

}

int Query(int x,int y,int val,int l,int r)

{

    if(l==r) return val/l+(val%l>0);  //对整除情况特殊处理

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

    int t=seg[seg[y].rs].sum-seg[seg[x].rs].sum;

    if(t>=val) return Query(seg[x].rs,seg[y].rs,val,mid+1,r);  //厚度范围是(mid+1,r)时足够

    else return Query(seg[x].ls,seg[y].ls,val-t,l,mid)+seg[seg[y].rs].cnt-seg[seg[x].rs].cnt;  //不够时

}

void solve2()

{

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

        S[i]=read(),Update(root[i-1],root[i],S[i],1,1000),S[i]+=S[i-1];   //以1~i-1的前缀树为模板建树

    while(q--)

    {

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

        if(S[y2]-S[y1-1]<h) puts("Poor QLW");

        else cout << Query(root[y1-1],root[y2],h,1,1000) << endl;

    }

}

int main()

{

    n=read();m=read();q=read();

    if(n>1) solve1();

    else solve2();

    return 0;

}

1、注意数据范围的特点

　如每个点数值的范围不大，可以考虑将 大于等于k的个数/总和 这样与数值范围相关的条件加入递推式中

2、如果 一个量是否符合要求具有单调性，可以对这个量二分答案

3、主席树：

大多数时候是离线的数据结构

需要知道数据的范围。每个节点维护的是1~i个数中处于数据范围[L,R]的数的信息。

也就是说每棵前缀树中维护的是数据范围[1,1000]的区间信息

4、注意x组成y至少要多少个这类问题的书写：

y=y/x+(y%x>0) || y=(y+x-1)/x

巴特西

[BZOJ 1926] 粟粟的书架

Solution:

Code:

最新文章

热门文章