题解：
这是两道题
前50%:
发现p[i][j]很小，于是记录f[i][j][k]表示（1，1）~（i，j）这个子矩阵内>=k的书的总高度,g[i][j][k]记录本数
查询是二分答案就好了
后50%:
主席树，右子树够了就向右走，否则向左走
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,T;
int PTsiz;
int root[500009];
struct PresidentTree{
int ls,rs,d,sum;
}tree[10000009];
void BuildTree(int &now,int l,int r){
now=++PTsiz;
tree[now].d=tree[now].sum=0;
if(l==r)return;
int mid=(l+r)>>1;
BuildTree(tree[now].ls,l,mid);
BuildTree(tree[now].rs,mid+1,r);
}
void Updatapoint(int &now,int pre,int p,int x,int l,int r){
now=++PTsiz;
tree[now]=tree[pre];
tree[now].d++;tree[now].sum+=x;
// cout<<"shit"<<tree[now].l<<‘ ‘<<tree[now].r<<endl;
if(l==r)return;
int mid=(l+r)>>1;
if(p<=mid)Updatapoint(tree[now].ls,tree[pre].ls,p,x,l,mid);
else Updatapoint(tree[now].rs,tree[pre].rs,p,x,mid+1,r);
}
int a[500009];
int b[500009],nn;
int sum2[500009];
int Queryamount(int now,int pre,int tot,int l,int r){
if(l==r){
int x=b[l];
if(tot%x==0)return tot/x;
else return tot/x+1;
}
int s=tree[tree[now].rs].sum-tree[tree[pre].rs].sum;
int d=tree[tree[now].rs].d-tree[tree[pre].rs].d;
// printf("%d %d %d %d
",b[tree[now].l],b[tree[now].r],d,s);
// if(s==tot)return d;
int mid=(l+r)>>1;
if(s<tot)return d+Queryamount(tree[now].ls,tree[pre].ls,tot-s,l,mid);
else return Queryamount(tree[now].rs,tree[pre].rs,tot,mid+1,r);
}
const int u=1000;
int f[209][209][u+10];//amount
int g[209][209][u+10];//sum
int c[209][209];
int Getans(int x,int y,int xx,int yy,int s){
int l=1,r=u,mid,ans=1;
while(l<=r){
mid=(l+r)>>1;
int tmp=g[xx][yy][mid]-g[xx][y-1][mid]-g[x-1][yy][mid]+g[x-1][y-1][mid];
if(tmp>=s){
ans=mid;l=mid+1;
}else{
r=mid-1;
}
}
int tmp=f[xx][yy][ans]-f[xx][y-1][ans]-f[x-1][yy][ans]+f[x-1][y-1][ans];
int tmp2=g[xx][yy][ans]-g[xx][y-1][ans]-g[x-1][yy][ans]+g[x-1][y-1][ans];
return tmp-(tmp2-s)/ans;
// return tmp;
}
int Workans1(){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&c[i][j]);
for(int k=0;k<=u;++k){
f[i][j][k]=f[i][j-1][k]+f[i-1][j][k]-f[i-1][j-1][k];
g[i][j][k]=g[i][j-1][k]+g[i-1][j][k]-g[i-1][j-1][k];
if(k<=c[i][j]){
f[i][j][k]+=1;
g[i][j][k]+=c[i][j];
}
}
}
}
while(T--){
int x,y,xx,yy,s;
scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&s);
int maxsum=g[xx][yy][0]-g[x-1][yy][0]-g[xx][y-1][0]+g[x-1][y-1][0];
if(maxsum<s)printf("Poor QLW
");
else printf("%d
",Getans(x,y,xx,yy,s));
}
}
int Workans2(){
for(int i=1;i<=m;++i){
scanf("%d",&a[i]);b[i]=a[i];sum2[i]=a[i]+sum2[i-1];
}
sort(b+1,b+1+m);
nn=unique(b+1,b+1+m)-b-1;
BuildTree(root[0],1,nn);
for(int i=1;i<=m;++i)Updatapoint(root[i],root[i-1],lower_bound(b+1,b+1+nn,a[i])-b,a[i],1,nn);
while(T--){
int x,y,xx,yy,s;
scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&s);
int tmp=Queryamount(root[yy],root[y-1],s,1,nn);
if(sum2[yy]-sum2[y-1]>=s)printf("%d
",tmp);
else printf("Poor QLW
");
}
}
int main(){
scanf("%d%d%d",&n,&m,&T);
if(n!=1)Workans1();
else Workans2();
return 0;
}