二合一题....

前面 $50$ 分：

考虑取书显然优先取厚的，所以答案满足单调性

发现 $P_{i,j}$ 不大，所以考虑二分最小厚度 $mid$，把大于等于 $mid$ 的书取走

维护 $cnt[i][j][k]$ 表示位置 $i,j$ 为右下角一直到 $1,1$ 的矩形内厚度大于等于 $k$ 的书的数量

维护 $sum[i][j][k]$ 表示位置 $i,j$ 为右下角一直到 $1,1$ 的矩形内厚度大于等于 $k$ 的书的总厚度

然后就可以愉快地二分答案了，注意最后要特判一下厚度为 $ans$ 的书不完全取完的情况！

后面 $50$ 分：

因为只有一行，考虑用主席树维护每个区间的所有值，然后处理询问在主席树上走就好了

同样注意特判最后一种厚度的书不完全取完的情况

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;inline int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }    return x*f;}const int N=207,M=5e5+7,INF=1e9+7;int n,m,Q;int cnt[N][N][1007],sum[N][N][1007];//sum是总和，cnt是数量int xa,ya,xb,yb,H,mx;inline int clac(int p) { return sum[xb][yb][p]-sum[xa-1][yb][p]-sum[xb][ya-1][p]+sum[xa-1][ya-1][p]; }//求一个矩形的suminline int CNT(int p) { return cnt[xb][yb][p]-cnt[xa-1][yb][p]-cnt[xb][ya-1][p]+cnt[xa-1][ya-1][p]; }//求一个矩形的cntinline int query()//二分答案{    int res=-1,l=0,r=mx+1,mid=l+r>>1;    while(l<=r)    {        mid=l+r>>1;        if(clac(mid)>=H) l=mid+1,res=mid;        else r=mid-1;    }    return res;}int bk[N][N];void solve1()//前面50分{    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++) bk[i][j]=read(),mx=max(mx,bk[i][j]);    for(int k=0;k<=mx;k++)        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)            {                sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+(bk[i][j]>=k ? bk[i][j] : 0);                cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]+(bk[i][j]>=k ? 1 : 0);            }    while(Q--)    {        xa=read(),ya=read(),xb=read(),yb=read(),H=read();        int t=query();        if(t==-1) printf("Poor QLW\n");        else printf("%d\n", CNT(t) - (clac(t)-H)/t );//注意特判厚度为t的书不全取    }}int t[M<<4],sz[M<<4],L[M<<4],R[M<<4],rt[M],tot;int res,val;inline void ins(int &o,int l,int r,int pre){    o=++tot; t[o]=t[pre]+val; sz[o]=sz[pre]+1;    int mid=l+r>>1;    if(l==r) return;    if(val<=mid) ins(L[o],l,mid,L[pre]),R[o]=R[pre];    else ins(R[o],mid+1,r,R[pre]),L[o]=L[pre];}inline void query(int hea,int las,int l,int r)//在主席树上走{    int mid=l+r>>1;    if(l==r)    {        res+= (val/l+(val%l!=0)) ;//注意特判        return;    }    if(t[R[las]]-t[R[hea]]<=val)//优先取大的    {        res+=sz[R[las]]-sz[R[hea]]; val-=t[R[las]]-t[R[hea]];        query(L[hea],L[las],l,mid);    }    else query(R[hea],R[las],mid+1,r);}inline void solve2()//后50分{    int l,r,a,b;    for(int i=1;i<=m;i++) val=read(),ins(rt[i],1,1000,rt[i-1]);    while(Q--)    {        a=read(),l=read(),b=read(),r=read(),val=read();        if(t[rt[r]]-t[rt[l-1]]
          
           1) solve1(); else solve2(); return 0;}